web前端算法简介之字典与哈希表

发布时间：2024年01月15日

回顾
- 栈、队列：进、出
  - 栈（Stack）：
    - 栈的操作主要包括：
  - 队列（Queue）：
    - 队列的操作主要包括：
- 链表、数组：多个元素存储组成的
字典与哈希表
前端算法题

回顾

栈、队列：进、出

栈（Stack）：

栈是一种线性数据结构，它遵循“后进先出”（Last In, First Out, LIFO）原则。在栈中，数据元素只能通过一个端点进行插入和删除操作，这个端点称为栈顶（top）。栈的特性是新添加的元素会放在所有已有元素之上，而移除元素时总是从栈顶开始移除最近添加的那个元素。

栈的操作主要包括：

Push（入栈）：将元素添加到栈顶。
Pop（出栈）：移除并返回栈顶元素。
Peek/Top（读栈顶）：查看栈顶元素但不移除。
IsEmpty（判断是否为空）：检查栈是否包含任何元素。

栈常用于实现函数调用、表达式求值、括号匹配等场景。

队列（Queue）：

队列也是一种线性数据结构，但它遵循的是“先进先出”（First In, First Out, FIFO）原则。在队列中，元素可以在一端（队尾）加入，而在另一端（队头）移除。

队列的操作主要包括：

Enqueue（入队）：在队列尾部添加一个元素。
Dequeue（出队）：从队列头部移除并返回一个元素。
Front（读队头）：查看队头元素但不移除。
IsEmpty（判断是否为空）：检查队列是否为空。

队列通常应用于多任务系统中的任务调度、消息传递、广度优先搜索算法等场合。队列可以采用顺序存储结构（如循环队列）或链式存储结构（如链队列）来实现。

链表、数组：多个元素存储组成的

简述

区别一：

数组：下标
链表：next指针联系在一起

区别二：数据插入

数组：如果在中间插入新的元素，其他元素会重新计算
链表：不会重新计算，说白了是赋值或者替换的一种感觉

区别三：查找

数组：通过下标进行查找即可
链表：每次查找都需要从头开始找

链表（Linked List）和数组（Array）是两种基本且重要的数据结构，它们在内存中的组织方式和操作特性有显著区别。

链表：

存储结构：链表中的元素不是连续存储的，每个元素（称为节点）包含两部分：数据域和指针域。数据域存储实际的数据，而指针域存储指向下一个节点的地址。
动态分配：链表的长度可以在程序运行时动态增长或缩短，不需要预先指定大小，新添加的元素可以动态地从堆中分配空间。
插入/删除：在链表中插入或删除一个元素相对容易，只需修改相应的指针即可，时间复杂度通常为O(1)（头插头删）至O(n)（在中间或尾部插入删除）。
访问速度：访问链表中的特定元素需要从头节点开始遍历，直到找到目标位置，因此随机访问的时间复杂度通常是O(n)，不如数组直接通过下标访问速度快。

数组：

存储结构：数组是一段连续的内存空间，其中每个单元存放一个元素，并可以通过索引（下标）直接访问。
静态分配：数组在声明时就需要确定其大小，一旦初始化后，大小就固定不变，所有元素占用连续内存空间。
插入/删除：在数组中插入或删除元素通常比较麻烦，因为可能需要移动后续元素以保持连续性，时间复杂度通常是O(n)。
访问速度：数组支持随机访问，即通过下标可以直接获取任何位置的元素，时间复杂度为O(1)。

适用场景：

链表适用于频繁进行插入、删除操作且对访问顺序要求不高的情况，例如实现队列、栈等数据结构以及某些动态变化的集合。
数组适用于元素数量已知并且需要快速随机访问的情况，如实现矩阵运算、查找算法等，也常用作缓存或其他固定大小的数据集存储。

更多详细内容，请微信搜索“前端爱好者“， 戳我查看 。

字典与哈希表

字典: 键值对存储的，类似于js的对象

字典 : 键值对存储的，类似于js的对象（键[key]都是字符串类型或者会转换成字符串类型）

字典是一种数据结构，它在计算机科学中用于存储键-值对（key-value pairs），其中每个键都是独一无二的，且与一个对应的值相关联。

这种数据结构允许通过键快速查找、添加和删除其关联的值。

字典常被比喻为现实生活中的字典，就像你通过单词（键）查找其定义（值）一样。

Python 中字典的定义和示例：

# 定义一个简单的字典
person = {
    "name": "John Doe",
    "age": 30,
    "city": "New York"
}

# 示例说明：
# - 键：字符串 "name"、"age" 和 "city"
# - 值：对应的值分别为字符串 "John Doe"、整数 30 和字符串 "New York"

# 访问字典中的值
print(person["name"])  # 输出: John Doe

# 修改或更新字典中的值
person["age"] = 31
print(person)  # 输出: {'name': 'John Doe', 'age': 31, 'city': 'New York'}

# 添加新的键值对
person["job"] = "Software Engineer"
print(person)  # 输出: {'name': 'John Doe', 'age': 31, 'city': 'New York', 'job': 'Software Engineer'}

# 判断键是否存在
if "city" in person:
    print("City is:", person["city"])

在上述例子中，person 字典是一个包含个人信息的数据结构，通过键（如“name”、“age”等）可以迅速获取到相应的值（如“John Doe”的姓名、30岁的年龄）。

一个例子

ar a = {}
var b = {
	key:'a'
}	
var c = {
	key:'c'
}
a[b] = '123';  // a[[object Object]] = '123'
a[c] = '456';	// a[[object Object]]  = '456'

console.log( a[b] );

结果：456，而不是123，为什么？

在JavaScript中，对象的覆盖规则遵循合并与替换的原则：

当一个对象被赋值给另一个对象或者通过扩展运算符（...）或Object.assign()方法合并到另一个对象时，如果两个对象有相同的属性名（键），则会发生以下情况：

简单类型属性：

如果原对象和新对象中存在相同名称的简单类型属性（如字符串、数字、布尔值等），那么新对象中的该属性值将覆盖原对象的相应属性值。

let obj1 = { a: 1, b: 'hello' };
let obj2 = { b: 'world', c: true };
let obj3 = { ...obj1, ...obj2 }; // 结果是 { a: 1, b: 'world', c: true }

在此例中，obj3 的 b 属性值来自 obj2，从而覆盖了 obj1 中的 b 属性值。

嵌套对象属性：

对于嵌套的对象属性，也是同样的原理。如果嵌套的对象结构中有相同的路径，则新的嵌套对象会覆盖原有的对象。

let obj1 = { nested: { a: 1 } };
let obj2 = { nested: { b: 2 } };
let obj3 = { ...obj1, ...obj2 }; // 结果是 { nested: { b: 2 } }

这里，obj3 的 nested 对象完全由 obj2 中的 nested 值覆盖，所以只包含 b: 2。

数组属性：

数组作为对象属性时，如果源对象和目标对象有同名数组属性，不会直接进行合并或替换，而是保持原有数组不变。若要合并数组元素，需要采用特定的方法，比如使用递归合并函数或者是展开操作符结合数组方法来实现数组元素的合并而非覆盖。

let obj1 = { array: [1, 2, 3] };
let obj2 = { array: [4, 5] };
let obj3 = { ...obj1, ...obj2 }; // 结果是 { array: [4, 5] }

在这个例子中，obj3.array 是 [4, 5] 而不是 [1, 2, 3, 4, 5]，因为这不是合并数组，而是简单的覆盖。

如果你希望合并数组内容而不是替换，可以使用自定义合并函数或者利用 Array.prototype.concat() 或 ES6 的扩展运算符加数组连接的方式来处理：

let obj1 = { array: [1, 2, 3] };
let obj2 = { array: [4, 5] };
let obj3 = { ...obj1, array: [...obj1.array, ...obj2.array] }; // 结果是 { array: [1, 2, 3, 4, 5] }

字典: map来表示的，map的键不会转换类型

字典 --> map来表示的，map的键不会转换类型

let map = new Map();
map.set('a','1');
map.set('b','2');
console.log( map );
console.log( map.get('b') ); 
console.log( map.has('x') );

map.delete('a');

console.log( map );

哈希表又叫 --> 散列表，在js中没有哈希表，哈希表是字典一种实现。

哈希表（Hash Table）是一种高效的数据结构，它通过散列函数（也称为哈希函数）将键（Key）映射到一个固定范围的索引数组中，然后将值（Value）存储在对应的数组位置上。

这样可以实现近乎常数时间复杂度（理想情况下为O(1)）的插入、删除和查找操作。

哈希表工作原理：

哈希函数：首先使用哈希函数将输入的键转换成一个整数值，这个过程被称为“哈希”或“散列”。理想的哈希函数应该满足以下条件：
- 确定性：对于相同的键总是生成相同的哈希值。
- 均匀分布：不同的键应尽可能均匀地分布在整个哈希空间内，以减少冲突。
哈希冲突：由于哈希函数输出范围有限，不同键可能产生相同的哈希值，这种现象称为哈希冲突。为了处理冲突，常见的策略有开放寻址法（如线性探测、二次探测等）、链地址法（每个数组元素指向一个链表，所有哈希值相同的键都在同一个链表中）以及再哈希法等。
负载因子与扩容：哈希表通常会设定一个最大负载因子（即已存储元素数量与表大小的比例），当负载因子超过某个阈值时，为了保持哈希表的性能，会进行动态扩容并重新哈希所有的元素。
操作时间复杂度：在理想情况下，哈希表的插入、删除和查找的时间复杂度都是O(1)，但在实际应用中，由于哈希冲突的存在，最坏情况下的时间复杂度可能达到O(n)。优秀的哈希函数和合适的冲突解决策略可以尽量降低这种情况发生的概率。

哈希表在编程语言中的常见应用包括字典、映射、关联数组等数据结构，它们广泛应用于数据库索引、缓存系统、唯一性检查等多个场景。

哈希表的工作原理和使用。

假设我们想要创建一个简单的电话簿，其中包含联系人的姓名（键）及其对应的电话号码（值）。

我们将使用哈希表作为数据结构，并且设计一个简单的哈希函数 hash(key) 来计算姓名对应的数组索引。

这里为了简化演示，我们将采用除留余数法的哈希函数，即 H(key) = key % capacity，其中capacity是哈希表数组的大小。

假设有以下联系人：

Alice, 电话：555-1234
Bob, 电话：555-5678
Carol, 电话：555-9012

我们选择哈希表的容量为10。

哈希函数示例：

H(“Alice”) = “Alice” % 10 = 0
H(“Bob”) = “Bob” % 10 = 2
H(“Carol”) = “Carol” % 10 = 2 （注意此处出现了冲突）

为了处理冲突，我们将采用线性探测法，当发现某个位置已经有元素时，就顺序检查下一个位置，直到找到空的位置。

构建哈希表的过程：

插入 Alice：

哈希地址 = H(“Alice”) = 0，该位置为空，所以将 (“Alice”, 555-1234) 存储在数组下标为0的位置。

插入 Bob：

哈希地址 = H(“Bob”) = 2，该位置也为空，所以将 (“Bob”, 555-5678) 存储在数组下标为2的位置。

插入 Carol：

哈希地址 = H(“Carol”) = 2，与 Bob 冲突。
使用线性探测，尝试下一个位置 (2+1)%10 = 3，这个位置也是空的，所以将 (“Carol”, 555-9012) 存储在数组下标为3的位置。

最终形成的哈希表可以表示如下（用“-”表示空槽位）：

Index:  | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
-------|---|---|---|---|---|---|---|---|---|---|
Value: | Alice | - | Bob | Carol | - | - | - | - | - | - |

在这个简化的例子中，通过哈希函数和冲突解决策略，我们可以快速查找、插入和删除电话簿中的记录。

例如，如果要查找Carol的电话号码，我们会首先对“Carol”进行哈希运算得到索引2，然后由于冲突继续探测到索引3，从而找到正确的电话号码。

哈希表与字典区别

区别一：如果找key对应的value需要遍历key，那么想要省去遍历的过程，用哈希表来表示。

区别二：排列顺序，字典是根据添加的顺序进行排列的

哈希表（Hash Table）与字典（Dictionary）是两种相似但有区别的数据结构，它们都是用于存储键值对的数据容器。下面总结了它们在不同编程语言环境中的主要区别：

泛型与非泛型：

哈希表：在某些编程语言中（如早期的C#），哈希表不是泛型集合，这意味着它能够存储任何类型的对象作为键和值，但在检索时需要类型转换。
字典：在很多现代编程语言如C#中，字典是泛型集合，它允许指定键和值的具体类型，从而在编译时提供类型安全，并且不需要额外的装箱和拆箱操作，提高了效率。

线程安全：

哈希表：在一些实现中，哈希表可能会设计为线程安全的，也就是说多个线程可以同时访问而不导致数据不一致或冲突。
字典：另一方面，许多编程语言的标准库中的字典类默认可能不是线程安全的，例如C#中的Dictionary类就不是线程安全的，若在多线程环境下使用，需要程序员自己确保同步机制（如使用锁）来保证线程安全。

性能与容量：

在单线程环境中，由于字典通常具有类型安全以及优化过的内部结构，因此在查找、插入和删除操作上往往比非泛型哈希表更快，空间利用率也更高。

命名空间和实现：

C# 中的 HashTable 类位于 System.Collections 命名空间下，而 Dictionary 类则位于 System.Collections.Generic 命名空间下，后者是.NET Framework 2.0 引入的泛型集合的一部分。

API 设计：

不同编程语言中，字典和哈希表可能提供了不同的方法集和接口设计，字典因为其泛型特性，可能拥有更简洁、更易于使用的API。

哈希表和字典的核心功能相同，都是基于哈希算法快速存取数据，但具体到某个编程语言和库中，它们的设计细节和使用场景会有所不同，字典倾向于提供更为现代、类型安全和高效的解决方案，而哈希表在某些情况下可能是为了向后兼容或是特定线程安全需求而存在的选择。

使用JavaScript实现一个hash表

class HashTable{

	constructor(){
		this.table = [];
	}
	hashCode( key ){
		let hash = 0;
		for( let i =0;i<key.length;i++){
			hash += key.charCodeAt(i);
		}
		return hash;
	}	
	put( key , val ){
		let hashKey = this.hashCode(key);
		this.table[ hashKey ] = val;
	}
	get( key ){
		let hashKey = this.hashCode(key);
		return this.table[hashKey];
	}
}

let hashTable = new HashTable();
hashTable.put('person','章三');
console.log( hashTable );
console.log(  hashTable.get('person') );

前端算法题

两数之和

leetcode： https://leetcode.cn/problems/two-sum/description/

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出和为目标值 target 的那两个整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

示例 1：

输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

示例 2：

输入：nums = [3,2,4], target = 6
输出：[1,2]

示例 3：

输入：nums = [3,3], target = 6
输出：[0,1]

提示：

2 <= nums.length <= 104
-109 <= nums[i] <= 109
-109 <= target <= 109
只会存在一个有效答案

进阶：你可以想出一个时间复杂度小于 O(n2) 的算法吗？

js解决方案1

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function (nums, target) {
    let map = new Map() // 新建Map

    // 遍历数组
    for (let i = 0; i < nums.length; i++) {
        // 定义一个差值
        let num = target - nums[i]
        // 如果map中包含这个值，则返回这个值索引和当前索引
        if (map.has(num)) {
            return [map.get(num), i]
        }

        // 保存当前值和当前索引
        map.set(nums[i], i)
    }
};

js解决方案2

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function (nums, target) {
    let index1, index2
    nums.forEach((num, i) => {
        nums.forEach((num1, j) => {
            if (num1 + num == target && i != j) {
                index1 = i;
                index2 = j
            }
        })
    })
    return [index1, index2]
};

js解决方案3

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {
    let obj = {}
    for(let i = 0; i <nums.length;i++ ){
        let num = nums[i]
        if(num in obj){
            return [obj[num],i]
        } else {
            obj[target-num] = i
        }
    }

};

217. 存在重复元素

leetcode地址：https://leetcode.cn/problems/contains-duplicate/description/

给你一个整数数组 nums 。如果任一值在数组中出现至少两次，返回 true ；如果数组中每个元素互不相同，返回 false 。

示例 1：

输入：nums = [1,2,3,1]
输出：true

示例 2：

输入：nums = [1,2,3,4]
输出：false

示例 3：

输入：nums = [1,1,1,3,3,4,3,2,4,2]
输出：true

提示：

1 <= nums.length <= 10^5
-10^9 <= nums[i] <= 10^9

js实现方案1

/**
 * @param {number[]} nums
 * @return {boolean}
 */
var containsDuplicate = function (nums) {
    // 新建一个字典

    let map = new Map()

    // 遍历数组
    for (const item of nums) {
        // 如果字典中有当前值，则返回true
        if (map.has(item)) {
            return true
        }

        // 把当前值保存到字典
        map.set(item, 1)
    }

    return false
};

js实现方案2

/**
 * @param {number[]} nums
 * @return {boolean}
 */
var containsDuplicate = function (nums) { 
 // 新建一个字典
  let set = new Set()
  // 遍历数组
  for (const item of nums) {
      // 如果字典中有当前值，则返回true
      if (set.has(item)) {
          return true
      }

      // 把当前值保存到字典
      set.add(item)
  }
  return false

};

扩展：ES6 Set数据类型

在JavaScript的ES6（ECMAScript 2015）中，Set 是一种新的数据结构类型，它类似于数组，但是成员的值都是唯一的，不存储重复的值。

这意味着当你向 Set 中添加元素时，如果该元素已经存在，则不会有任何变化，Set的大小也不会增加。

创建 Set 的基本语法是使用 new Set() 构造函数，并传入一个可迭代对象（如数组或其他 iterable 对象）：

// 创建一个新的空 Set
const emptySet = new Set();

// 创建一个包含若干唯一值的 Set
const numbersSet = new Set([1, 2, 3, 4, 4, 5]); // 注意：尽管有两次 '4'，但只会存储一次
console.log(numbersSet.size); // 输出: 5

// 创建一个包含字符串的 Set
const wordsSet = new Set(["apple", "banana", "apple"]); // 只有一个 "apple"

Set 提供了一些方法用于操作其内容：

add(value): 向 Set 添加一个新值，如果值已存在则不执行任何操作。
delete(value): 从 Set 中删除指定的值。
has(value): 检查 Set 是否包含某个值，返回布尔结果。
clear(): 清除 Set 中的所有元素。
size: 属性，返回 Set 中元素的数量。

例如：

let fruits = new Set(["apple", "banana", "cherry"]);

fruits.add("orange"); // 添加一个元素
console.log(fruits.has("banana")); // true，检查是否包含 "banana"
fruits.delete("apple"); // 删除 "apple"
console.log(fruits.size); // 输出当前 fruits Set 的元素数量

扩展：ES6 中 set和map 的区别

在JavaScript的ES6中，Set和Map是两种不同的数据结构类型，它们各自有独特的用途和操作方法：

Set（集合）

Set是一个特殊的类型，它存储的是唯一不重复的值序列。Set中的元素没有键值对的概念，每个元素自身既是键也是值。
特点：
- 不允许出现重复值，自动去重。
- 集合内的元素是无序的，尽管实际实现可能按照某种内部顺序排列，但不能通过索引访问。
- 提供了add, delete, has, clear等方法用于操作集合元素。

let set = new Set();
set.add(1); // 添加数字1
set.add('apple'); // 添加字符串'apple'
set.has(1); // 返回true，判断是否存在
set.delete('apple'); // 删除字符串'apple'
console.log(set.size); // 输出当前集合内元素的数量

Map（映射）

Map是一个键值对的数据结构，类似于对象，但它允许任何类型的值（包括对象）作为键，并且键值对的顺序是可以被保留的。
特点：
- 键值对的形式存储数据，键必须是唯一的，值可以重复。
- 可以通过键来获取对应的值，使用get(key)方法。
- 提供了set(key, value), get(key), delete(key), has(key), clear()等方法，以及迭代方法如entries(), keys(), values()。

let map = new Map();
map.set('name', 'Alice'); // 添加键值对
map.set({id: 1}, 'Bob'); // 对象也可以作为键
console.log(map.get('name')); // 获取键为'name'的值：'Alice'
map.delete({id: 1}); // 删除特定键的键值对
console.log(map.has({id: 1})); // 检查是否包含给定键，返回布尔值

总结起来，Set主要用于存储一组唯一的、无需有序的值，而Map则用于存储和检索基于任意值关联的数据，保持插入时的键值对顺序。

349. 两个数组的交集

leetcode地址：https://leetcode.cn/problems/intersection-of-two-arrays/description/

给定两个数组 nums1 和 nums2 ，返回它们的交集。输出结果中的每个元素一定是唯一的。我们可以不考虑输出结果的顺序。

示例 1：

输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2]

示例 2：

输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出：[9,4]
解释：[4,9] 也是可通过的

提示：

1 <= nums1.length, nums2.length <= 1000
0 <= nums1[i], nums2[i] <= 1000

js实现方案

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number[]}
 */
var intersection = function (nums1, nums2) {

    // 先把数组去重
    let set1 = new Set(nums1)
    let set2 = new Set(nums2)

    // 然后把第一个去重后的数据转成数组，便于使用filter方法
    let finalNums1 = [...set1]

    // 返回重复数据
    return finalNums1.filter((item) => set2.has(item))
};

1207. 独一无二的出现次数

引子

判断一个字符串中出现次数最多的字符，并统计次数

例如：nums = ‘aaabbbbccccccc’

解决方案

function fun( s ){
	let maxNum = 0;
	let maxStr = '';
	let map = new Map();
	for( let item of s ){
		map.set( item , (map.get(item) || 0 ) + 1 )
	}

	for(let [key,value] of map){
		if( value > maxNum ){
			maxStr = key;
			maxNum = value;
		}
	}
	return [maxStr , maxNum];
}

console.log( fun('aaabbbbccccccc') );

1207. 独一无二的出现次数

leetcode地址：https://leetcode.cn/problems/unique-number-of-occurrences/description/

给你一个整数数组 arr，请你帮忙统计数组中每个数的出现次数。

如果每个数的出现次数都是独一无二的，就返回 true；否则返回 false。

示例 1：

输入：arr = [1,2,2,1,1,3]
输出：true
解释：在该数组中，1 出现了 3 次，2 出现了 2 次，3 只出现了 1 次。没有两个数的出现次数相同。

示例 2：

输入：arr = [1,2]
输出：false

示例 3：

输入：arr = [-3,0,1,-3,1,1,1,-3,10,0]
输出：true

提示：

1 <= arr.length <= 1000
-1000 <= arr[i] <= 1000

js解决方案

/**
 * @param {number[]} arr
 * @return {boolean}
 */
var uniqueOccurrences = function (arr) {
    // 定义一个字典
    const map = new Map()

    // 遍历数组
    for (const item of arr) {
        //判断map中是否有当前项
        if (map.has(item)) {
            // 如果有，则加一
            map.set(item, map.get(item) + 1)
        } else {
            // 如果没有，则存储
            map.set(item, 1)
        }
    }

    // 定义一个set
    const set = new Set()

    // 遍历字典，根据Set数据的去重性质，把数据填充到Set中
    for (let [key, value] of map) {
        set.add(value)
    }

    // 判断二者长度是否相等
    return map.size == set.size

};

3. 无重复字符的最长子串

leetcod地址：https://leetcode.cn/problems/longest-substring-without-repeating-characters/description/

给定一个字符串 s ，请你找出其中不含有重复字符的最长子串的长度。

示例 1:

输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

示例 2:

输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

示例 3:

输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

提示：

0 <= s.length <= 5 * 10^4
s 由英文字母、数字、符号和空格组成

扩展：滑动窗口

滑动窗口是一种在计算机科学中广泛使用的抽象概念，主要应用于数据流处理、序列算法等领域。

它提供了一种以固定大小的“窗口”查看数据流的方式，随着数据流的推进，“窗口”会从初始位置开始向前滑动，并不断更新窗口内的数据。

具体来说，假设我们有一个数据流（如一个数组或列表），窗口大小为k，那么在任意时刻，窗口都会包含数据流中最近的k个元素。

当新的元素进入数据流时，窗口会向前滑动一位，并将最早进入窗口的那个元素移出窗口，同时将新元素纳入窗口。

滑动窗口常用于解决诸如求解子数组和、最大/最小值、中位数等问题，在网络流量控制、数据平滑、在线统计分析等方面也有广泛应用。

例子：求给定数组的每个长度为k的连续子数组的最大值

滑动窗口算法在JavaScript中的应用可以用来解决许多与数组或序列相关的高效问题，例如求解连续子数组的最大值、最小值、平均值、中位数等。

以下是一个使用滑动窗口解决“求给定数组的每个长度为k的连续子数组的最大值”的例子：

// JavaScript 滑动窗口实现：找出所有长度为 k 的连续子数组的最大值
function maxInWindows(nums, k) {
  const result = [];
  // 初始化一个单调递减栈来保存窗口内的最大值及其索引
  let stack = [];
  
  // 右指针遍历数组
  for (let right = 0; right < nums.length; right++) {
    // 移除窗口左侧不在范围内的元素对应的索引
    while (stack.length > 0 && right - stack[0][1] >= k) {
      stack.shift();
    }
    
    // 当栈为空或者当前元素大于栈顶元素时，更新栈顶最大值
    if (stack.length === 0 || nums[right] > nums[stack[stack.length - 1][1]]) {
      stack.push([nums[right], right]);
    }

    // 如果右指针已经滑动到了窗口内（即right >= k-1），那么可以计算并添加结果
    if (right >= k - 1) {
      result.push(stack[0][0]); // 栈顶元素始终是当前窗口的最大值
    }
  }

  return result;
}

// 示例用法：
const nums = [2, 3, 4, 2, 6, 2, 5, 1];
const k = 3;
console.log(maxInWindows(nums, k)); // 输出: [4, 6, 6, 5]

在这个例子中，我们维护了一个单调栈，其中存储的是窗口内遇到的最大值及其所在的索引。

随着右指针向右移动，不断调整栈中的元素以保持栈顶元素始终为当前窗口的最大值。

当窗口滑动到有效范围时，即可从栈顶获取该窗口的最大值，并将其添加到结果数组中。

js解决方案1

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function (s) {
    // 新建一个hash表
    const map = new Map()

    //左指针
    let left = 0

    // 最长字串的结果值
    let num = 0

    // 遍历字符串
    for (let i = 0; i < s.length; i++) {
        // map中是否有当前值
        if (map.has(s[i]) && map.get(s[i]) >= left) {
            left = map.get(s[i]) + 1
        }
        num = Math.max(num, i - left + 1) //  i - left + 1: 取的是长度，所以要 +1

        // 如果map中没有，则存储
        map.set(s[i], i)
    }

    return num
};

js解决方案2

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function(s) {
    // 思路：
    // 1. 先进行右侧指针（窗口）移动位置（后移）
    // 2. 判断是否符合预期。
    //  2.1 符合，进行其他处理，比如reurn等
    //  2.2 不符合，左侧指针是否移动位置
    //      2.2.1 移动或着不移动
    // 3. 进入下一次循环

    if(s.length <=1){
        return s.length 
    }

    //定义指针
    let left = 0
    let right = 1

    // 定义无重复最长字串
    let max = 0

    // 定义字串
    let temp

    // 当且仅当右侧指针向右侧移动不超过s
    while(right < s.length){
        temp = s.slice(left,right) // splice(0,1)
        // 判断当前元素是否包含right所在位置下表元素
        if(temp.indexOf(s.charAt(right)) > -1){
            left ++
            continue
        } else {
            right ++
        }

        if(right - left > max){
            max = right - left
        } 
    }

return max 
};

文章来源:https://blog.csdn.net/BradenHan/article/details/135589995
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若内容造成侵权/违法违规/事实不符，请联系我的编程经验分享网邮箱：chenni525@qq.com进行投诉反馈，一经查实，立即删除！

web前端算法简介之字典与哈希表

回顾

栈、队列 ： 进、出

栈（Stack）：

栈的操作主要包括：

队列（Queue）：

队列的操作主要包括：

链表、数组 ： 多个元素存储组成的

简述

链表：

数组：

适用场景：

字典与哈希表

字典: 键值对存储的，类似于js的对象

一个例子

在JavaScript中，对象的覆盖规则遵循合并与替换的原则：

字典: map来表示的，map的键不会转换类型

哈希表 又叫 --> 散列表 ， 在js中没有哈希表，哈希表是字典一种实现。

哈希表的工作原理和使用。

哈希表与字典区别

使用JavaScript实现一个hash表

前端算法题

两数之和

217. 存在重复元素

扩展：ES6 Set数据类型

扩展：ES6 中 set和map 的区别

349. 两个数组的交集

1207. 独一无二的出现次数

引子

1207. 独一无二的出现次数

3. 无重复字符的最长子串

扩展：滑动窗口

例子：求给定数组的每个长度为k的连续子数组的最大值

栈、队列：进、出

链表、数组：多个元素存储组成的

哈希表又叫 --> 散列表，在js中没有哈希表，哈希表是字典一种实现。