leetcode热题hot100【JS】

更新时间

2024.5.12 第一次更新

2024.5.17 第二次更新

刷算法题可能用到的函数和表示方式

常用的表达方式

1 2	//2的10次方 let n = 2 ** 10;

数组

//数组中插入数据
let arr = [];
arr.push(1);

//arr = [1]
arr.indexOf(1);//0


//比较两个数组是否相等（只适用于数组里面的元素都是原始值）
function arraysAreEqual(array1, array2) {
    // 首先检查数组长度
    if (array1.length !== array2.length) return false;

    // 然后检查每个元素是否相等
    for (let i = 0; i < array1.length; i++) {
        if (array1[i] !== array2[i]) return false;
    }

    // 如果通过了上述检查，那么数组相等
    return true;
}

//数组遍历
let strs = ["hello", "world", "JavaScript"];

//使用for循环
for(let i = 0; i < strs.length; i++){
  console.log(i,strs[i]);
}

//使用for of 与entries()
for (let [i, str] of strs.entries()) {
    console.log(i, str);
}

//数字数组的排序
//在JavaScript中，如果sort()方法没有提供比较函数，它会将数组元素转换成字符串，然后按照字符串的Unicode码点顺序进行排序。
//会导致例如这个数组[100,4,200,1,3,2]排序不成功
//例如，数字100和200在转换为字符串后，会根据它们的第一个字符（"1"和"2"）来进行排序，但当比较2和100时，由于"2"的Unicode码点小于"1"的Unicode码点，所以2会排在100之前。
//需要加入比较函数
nums = [100,4,200,1,3,2];
nums.sort((a, b) => a - b);
//这个比较函数简单地从a中减去b。如果结果是负数，那么a将排在b之前；如果结果是正数，b将排在a之前；如果结果是0，那么它们的顺序不变。
// a-b就是 从小到大排序


//初始化一个长度为n，值为0的数组
let n = 5; // 假设我们想要一个长度为5的数组
let arr = Array(n).fill(0);
console.log(arr); // 输出: [0, 0, 0, 0, 0]

字符串

//单个字符转换成ASCII码字
let c = 'a';
let ASCIINum = c.charCodeAt(0);//97

let c1 = 'ab';
let ASCIINum = c.charCodeAt(2);//98

//将字符串分割成单个字符的数组
let str = "hello";
str.split("").forEach(char => console.log(char));
// ['h','e','l','l','o']

//字符串字母排序 
function sortString(str) {
    // 将字符串转换为数组
    let arr = str.split('');
    // 对数组进行排序
    arr.sort();
    // 将数组转换回字符串
    return arr.join('');
}

let originalString = "hello";
let sortedString = sortString(originalString);

console.log(sortedString); // 输出: ehllo

Map

在JavaScript中，Map 是一种新的数据结构，它允许你存储键值对（key-value pairs）。与对象不同，Map 的键可以是任何类型的值，包括函数、对象或任何原始类型。下面是一些基本的 Map 对象用法：

//使用 `has` 方法可以检查 `Map` 中是否存在某个键：
//创建一个 Map
let map = new Map();

//设置键值对
//使用 `set` 方法可以添加或更新键值对：
map.set('key', 'value');
map.set(123, 456);
map.set({}, 'Object');
map.set(function() {}, 'Function');

//获取值
console.log(map.get('key')); // 输出: 'value'
console.log(map.get(123)); // 输出: 456

//检查键是否存在
console.log(map.has('key')); // 输出: true
console.log(map.has('notExist')); // 输出: false

//删除键值对
map.delete('key');

//获取Map的大小
//使用 `size` 属性可以获取 `Map` 中键值对的数量：
console.log(map.size);

//遍历Map
//`Map` 对象可以通过 `forEach` 方法遍历，也可以使用迭代器方法（如 `keys()`, `values()`, 和 `entries()`）进行遍历。

//使用 `forEach` 遍历：
map.forEach((value, key) => {
  console.log(key, value);
});

//使用迭代器遍历：
for (let [key, value] of map.entries()) {
    console.log(key, value);
}

// 或者直接遍历Map对象
for (let [key, value] of map) {
    console.log(key, value);
}

//清空Map
map.clear();

Set

在JavaScript中，Set是一种新的数据结构，它类似于数组，但是它的一个主要特点是其内部的值都是唯一的，没有重复的值。Set对象允许你存储任何类型的唯一值，无论是原始值或是对象引用。

//创建一个 Set
let mySet = new Set();

//也可以在创建时初始化`Set`：
let mySet = new Set([1, 2, 3, 4, 4, 4]);
console.log(mySet); // Set(4) {1, 2, 3, 4}


//注意，即使数组中包含重复的元素，`Set`仍然确保只保存唯一的值。
//添加元素
mySet.add(5);
mySet.add("hello");
mySet.add({a: 1, b: 2});

//检查元素
console.log(mySet.has(1)); // true
console.log(mySet.has(6)); // false

// 删除元素
mySet.delete(1);

//遍历 Set
//`Set`对象可以使用`forEach()`方法和`for...of`循环来遍历：
mySet.forEach(value => {
    console.log(value);
});

for (let item of mySet) {
    console.log(item);
}

//获取 Set 的大小
console.log(mySet.size);

//清空 Set
mySet.clear();

Set是JavaScript ES6中引入的一种集合类型，它提供了一种存储唯一值的高效方式。

100题实战

哈希

两数之和【数组、哈希】

1. 两数之和

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

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

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

示例 1：

1
2
3

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

示例 2：

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

示例 3：

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

提示：

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

code:

第一次写没有考虑到两个数的下标不能一样

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {
    for(let i = 0; i < nums.length; i++){
        let res = [];
        let index;
        if(( index = nums.indexOf(target - nums[i])) != -1 && index != i){
            res.push(i);
            res.push(index);
            return res;
        }
    }

};

字母异位词分组【数组、哈希、字符串】

49. 字母异位词分组

给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。

字母异位词 是由重新排列源单词的所有字母得到的一个新单词。

示例 1:

1 2	输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"] 输出: [["bat"],["nat","tan"],["ate","eat","tea"]]

示例 2:

1 2	输入: strs = [""] 输出: [[""]]

示例 3:

1 2	输入: strs = ["a"] 输出: [["a"]]

提示：

1 <= strs.length <= 104
0 <= strs[i].length <= 100
strs[i] 仅包含小写字母

code

一开始的想法是对每一个字符串的ASCII码求和，和一样的字符串就是字母异位词，但是仔细想一下就知道这样不对，即使字符不一样，也可能会出现SASCII码一样的情况

//错误的
/**
 * @param {string[]} strs
 * @return {string[][]}
 */
var groupAnagrams = function(strs) {
    let hash = new Map();
    for(let i = 0; i < strs.length; i++){
        //遍历每一个字符串
        let sumASCII = 0;
        strs[i].split('').forEach(c => sumASCII += c.charCodeAt(0));
        
        if(hash.has(sumASCII)){//存在同样的
            let arr = hash.get(sumASCII);
            arr.push(strs[i]);
            hash.set(sumASCII, arr);
        }else{
            let arr = [];
            arr.push(strs[i]);
            hash.set(sumASCII,arr);
        }
    }
    let res = [];
    hash.forEach( (value, key) => {
        res.push(value);
    });
    return res;
};

看了官方解法,有两种解法，排序和计数，很好的解法

排序

思路和上面的ASCII码的思路是一样的

/**
 * @param {string[]} strs
 * @return {string[][]}
 */
var groupAnagrams = function(strs) {
    let mp = new Map();//哈希表，<str, arr>

    for(let [i, str] of strs.entries()){
        //排序
        let arr = str.split('').sort();
        let newStr = arr.join('');

        if(mp.has(newStr)){//存过了
            let subArr = mp.get(newStr);
            subArr.push(str);
            mp.set(newStr, subArr);
        }else{
            let subArr = [];
            subArr.push(str);
            mp.set(newStr, subArr);
        }
    }

    let res = [];
    mp.forEach((value, key) => res.push(value));
    return res;

};

【要二刷】最长连续序列【并查集、数组、哈希表】

128. 最长连续序列

给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。

请你设计并实现时间复杂度为 O(n) 的算法解决此问题。

示例 1：

1
2
3

输入：nums = [100,4,200,1,3,2]
输出：4
解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。

示例 2：

1 2	输入：nums = [0,3,7,2,5,8,4,6,0,1] 输出：9

提示：

0 <= nums.length <= 105
-109 <= nums[i] <= 109

思路是哈希表，但是刚开始没有想到有负数，通过用例 67/75

主要是超过时间限制了，10的9次方的数，遍历一遍就超时了

单出用hashtable[num]++;来计数判断不行了

//个别用例超时
/**
 * @param {number[]} nums
 * @return {number}
 */
var longestConsecutive = function(nums) {
    if(nums.length===0) return 0;
    let maxNum = 0;
    let minNum = 0;
    nums.map( (v) =>{
        maxNum = Math.max(maxNum, v);
        minNum = Math.min(minNum, v);
    });
    //
    let hashTable1 = Array(maxNum + 1).fill(0);
    let hashTable2
    if(minNum < 0){//有负数
        hashTable2 = Array( -1 * minNum + 1).fill(0);
    }
    
    for(let i = 0; i < nums.length; i++){
        if(nums[i] >= 0){
            hashTable1[nums[i]]++;
        }else{
            hashTable2[ -1 * nums[i]]++;
        }
    }
    
    let res = 0;

    let maxLen1 = -1;
    let maxLen2 = -1;
    let l1 = 0;
    let l2 = 0;
    //正数
    let f1 = false;
    for(let i = 0; i <= maxNum ; i++){
        if(hashTable1[i] != 0){
            res++;
        }else{//有中断
            f1 = true;
            maxLen1 = Math.max(maxLen1, res);
            res = 0;//重新计数
        }
        if(!f1) l1++;
    }
    maxLen1 = Math.max(maxLen1, res);
    //负数
    res = 0
    let f2 = false;
    for(let i = 1; i <= ( -1 * minNum) ; i++){
        if(hashTable2[i] != 0){
            res++;
        }else{//有中断
            f2 = true;
            maxLen2 = Math.max(maxLen2, res);
            res = 0;//重新计数
        }
        if(!f2) l1++;    
    }
    maxLen2 = Math.max(maxLen2, res);

    //计算负-0-正

    return Math.max(maxLen1, maxLen2, l1+l2);

};

稍微看了一下题解思路，说是主要判断这个数的上一个数是否在哈希表中，感觉有点思路了，尝试写一下,没写出来，看完题解思路了才写的

/**
 * @param {number[]} nums
 * @return {number}
 */
var longestConsecutive = function(nums) {
    let mySet = new Set();
    nums.map( v => {mySet.add(v);});
    let res = 0, cn = 1;
    for(let i = 0; i < nums.length; i++){
        //判断该数字是否是连续子串的开头
        cn = 1;
        if(!mySet.has(nums[i] - 1)){//是开头
            let st = nums[i] + 1;
            while(mySet.has(st)){
                cn++;
                st++;
            }
            res = Math.max(res, cn);
        }
    }
    return res;
};

双指针

移动零【数组、双指针】

283. 移动零

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

请注意 ，必须在不复制数组的情况下原地对数组进行操作。

示例 1:

1 2	输入: nums = [0,1,0,3,12] 输出: [1,3,12,0,0]

示例 2:

1 2	输入: nums = [0] 输出: [0]

提示:

1 <= nums.length <= 104
-231 <= nums[i] <= 231 - 1

进阶：你能尽量减少完成的操作次数吗？

code

快慢指针的思路

慢指针指向待更新的数

快指针指向非0需要转移的数

/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var moveZeroes = function(nums) {
    // 0 1 0 3 12
    //在 0 的位置对非 0 赋值
    let len = nums.length;
    let f = 0, s = 0;
    for(s = 0; s < len; s++){
        while( f < len && nums[f] == 0) f++;
        if(f >= len) break;
        nums[s] = nums[f++];
    }
    while(s<len){
        nums[s++] = 0;
    }
    return nums;
    
};

盛最多水的容器【双指针、贪心】

11. 盛最多水的容器

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。

找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

返回容器可以储存的最大水量。

说明：你不能倾斜容器。

示例 1：

1
2
3

输入：[1,8,6,2,5,4,8,3,7]
输出：49 
解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。

示例 2：

1 2	输入：height = [1,1] 输出：1

提示：

n == height.length
2 <= n <= 105
0 <= height[i] <= 104

code：

前几天刚做过，复习了一下

双指针，两边夹

贪心的想法，由于装水的面积是右桶的长短决定的，所以较短的那条边先向中间走（这是保证从长到短的宽度下的最优解）

/**
 * @param {number[]} height
 * @return {number}
 */
var maxArea = function(height) {
    let maxNum = -1;
    let st = 0, end = height.length - 1;
    while(st < end){
        maxNum = Math.max(maxNum, (end - st) * Math.min(height[st], height[end]));
        if(height[st] <= height[end]){
            st++;
        }else end--;
    }
    return maxNum;
};

【优先二刷】三数之和【数组，双指针】

15. 三数之和

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请

你返回所有和为 0 且不重复的三元组。

注意：答案中不可以包含重复的三元组。

示例 1：

输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
解释：
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意，输出的顺序和三元组的顺序并不重要。

示例 2：

1
2
3

输入：nums = [0,1,1]
输出：[]
解释：唯一可能的三元组和不为 0 。

示例 3：

1
2
3

输入：nums = [0,0,0]
输出：[[0,0,0]]
解释：唯一可能的三元组和为 0 。

提示：

3 <= nums.length <= 3000
-105 <= nums[i] <= 105

code：

排序去重是一个很重要的点，有很多题目，都是组成元素一样，但是顺序不一样，此时，应该考虑排序

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var threeSum = function(nums) {
    let res = [];
    let set = new Set();
    for(let i = 0; i < nums.length; i++){
       for(let j = i; j < nums.length; j++){
            if( i != j){
                let sum = nums[i] + nums[j];
                let index = nums.indexOf(-sum);
                if(index != -1 && index != i && index != j){ 
                    let arr = []; 
                    arr.push(nums[i]);
                    arr.push(nums[index]);
                    arr.push(nums[j]);              
                    arr.sort();
                    if(!set.has(arr)){
                        res.push(arr);
                        set.add(arr);
                    }     
                }
            }
       } 
    }
    return res;
};

但是这样写的话在JS中是不能用set去重的，因为set中的元素是对象，对象引用的是指针，就算排序后的数组中的每一个元素都是一样的，set也会认为这是不同的数组。然后尝试将数组使用join函数转换为字符串在传入set去重

但是还是有问题，测试用例过227/313，不知道哪里错了，看不出来.

还有效率问题：您的代码使用了三层循环（实际上是两层循环加一个线性搜索 indexOf），这导致时间复杂度高达 O(n^3)，在 nums 数组较大时会非常低效。

思考：其实经常想不到sort排序的解法，应该想到的

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var threeSum = function(nums) {
    let res = [];
    let set = new Set();
    for(let i = 0; i < nums.length; i++){
       for(let j = i; j < nums.length; j++){
            if( i != j){
                let sum = nums[i] + nums[j];
                let index = nums.indexOf(-sum);
                if(index != -1 && index != i && index != j){ 
                    let arr = []; 
                    arr.push(nums[i]);
                    arr.push(nums[index]);
                    arr.push(nums[j]);              
                    arr.sort();
                    let str = arr.join('');
                    if(!set.has(str)){
                        res.push(arr);
                        set.add(str);
                    }     
                }
            }
       } 
    }
    return res;
};

转换思路，咨询了一下AI模型，跑了后还是对的

排序：首先对数组进行排序，这样可以更容易地避免重复的三元组，并且可以使用双指针技术来减少不必要的搜索。

双指针：使用一个外层循环遍历每个元素，然后在剩余部分使用两个指针（一个从左边开始，另一个从右边开始）来寻找两个数，使得这三个数的和为0。

跳过重复元素：在外层循环和双指针移动时，如果遇到相同的元素，应该跳过，以避免重复的三元组。

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var threeSum = function(nums) {
    //排序+循环嵌套双指针（两边夹）
    //因为有重复元素，还要去重
    nums.sort((a,b) => a - b);//递增
    let res = [];
    for(let i = 0; i < nums.length - 2; i++){//-2时因为i是三元组的第一个，要构成三元组就不可能是最后一个
        //对于三元组中的第一个数，也要去重，同一个数，只操作一次
        if( i > 0  && nums[i] == nums[i - 1]) continue;
      //if( i + 1 < nums.length - 2 && nums[i + 1] == nums[i]) continue;这样的去重逻辑是错误的，不要这样写
        //双指针两边夹
        let left = i + 1, right = nums.length - 1;
        while(left < right){
            let sum = nums[i] + nums[left] + nums[right];
            if(sum === 0){//找到一个三元组
                res.push([nums[i], nums[right], nums[left]]);
                while(left < right && nums[left] == nums[left + 1]) left++;
                while(left < right && nums[right] == nums[right - 1]) right--;
                left++;
                right--;
            }else if(sum < 0){
                left++;
            }else right--;
        }
    }
    return res;
};

【！！dp，还没写】接雨水

42. 接雨水

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

示例 1：

1
2
3

输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。

示例 2：

1 2	输入：height = [4,2,0,3,2,5] 输出：9

提示：

n == height.length
1 <= n <= 2 * 104
0 <= height[i] <= 105

滑动窗口

无重复字符的最长子串

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

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

示例 1:

1
2
3

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

示例 2:

1
2
3

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

示例 3:

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

提示：

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

code:

不用map，用set和单纯数组都行，数组的话就用include方法来查看字母是否已经存在于数组中，但是最好还是不要数组了，数组里面删除一个元素会很麻烦，主要还是哈希+滑动窗口的思想。

用set的话会简单一点点

带注释版本

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function(s) {
    if(s.length==0) return 0;
    //无重复字符的最长子串
    //ex
    // abcabcbb
    // abc -> maxLen = 3
    //滑动窗口
    //1.定义需要维护的变量
    let maxLen = -1;
    let hash = new Map();
    //2.定义窗口的首尾端，然后滑动窗口
    let st = 0;
    for(let end = 0; end < s.length; end++){//第一次debug是end++写成s++了
        //维护变量
        let c = s[end];
        
        //情况2:窗口可变,检查窗口是否合法，不合法就调整st指针直至合法  
        //在该题目中，不合法指的是，字符串中出现重复字符 
        if(hash.has(c)){//c字符不是第一次出现，窗口不合法
            //只要连续移动字符，直到新的窗口的字符中不包含第一次出现的c字符位置
            while( st < end && s[st] != c){
                hash.delete(s[st]);//第二次debug，这一句和下面一句的顺序反了，如果先++在delet，那么相当于delet的是下一个字符，第一个字符永远都不会被移除
                st++;
            } 
            //此时的st应该位于第一个窗口的第一个c字符处
            st++;
            //现在窗口合法了
        }else{//第一次出现
            hash.set(c, 1);
        }

        //窗口的长度为end - st + 1 （左闭右闭区间）
        //如果是左闭右开区间，就是end - st
        maxLen = Math.max(maxLen, end - st + 1);
    }
    return maxLen;
};

不带注释

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function(s) {
    if(s.length==0) return 0;
    let maxLen = -1;
    let hash = new Map();
    let st = 0;
    for(let end = 0; end < s.length; end++){
        let c = s[end];    
        if(hash.has(c)){
            while( st < end && s[st] != c){
                hash.delete(s[st]);
                st++;
            } 
            st++;
        }else{
            hash.set(c, 1);
        }
        maxLen = Math.max(maxLen, end - st + 1);
    }
    return maxLen;
};

找到字符串中所有字母异位词

438. 找到字符串中所有字母异位词

给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。

异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。

示例 1:

输入: s = "cbaebabacd", p = "abc"
输出: [0,6]
解释:
起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。
起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。

示例 2:

输入: s = "abab", p = "ab"
输出: [0,1,2]
解释:
起始索引等于 0 的子串是 "ab", 它是 "ab" 的异位词。
起始索引等于 1 的子串是 "ba", 它是 "ab" 的异位词。
起始索引等于 2 的子串是 "ab", 它是 "ab" 的异位词。

Code:

窗口不合理的情况比较复杂

带注释版本

/**
 * @param {string} s
 * @param {string} p
 * @return {number[]}
 */
var findAnagrams = function(s, p) {
    //哈希(异位词)+滑动窗口(子串)
    //异位词的特点是：
    //1.长度相等
    //2.每个字符的出现次数相等
    let hash = new Map();
    let hash2 = new Map();
    let res = [];
    //初始化hash
    for(let i = 0; i < p.length; i++){
        if(hash.has(p[i])){
            hash.set(p[i], hash.get(p[i]) + 1);
        }else hash.set(p[i], 1);
    }
    //初始化窗口，并开始滑动
    let st = 0;
    for(let end = 0; end < s.length; end++){
        let c = s[end];
        if(hash2.has(c)){
            hash2.set(c, hash2.get(c) + 1);
        }else hash2.set(c, 1);

        //窗口不合法1，没有这个字符,两个指针都跳到这个指针后面
        if(!hash.has(c)){
            while(st != end + 1){//debug1,一开始没有跳转到st = end+1，只是st++，这样是不对的，而且跳转完之后，一定要记得移除hash2中前面的（已经不在滑动窗口中的）字母
                hash2.set(s[st], hash2.get(s[st]) - 1);
                st++;
            }
        }else if(hash2.get(c) > hash.get(c)){
            //窗口不合法2,有这个字符，但是字符数多了,移动st，直到窗口中的c的字符数与hash中的字符数一致
            while(hash2.get(c) != hash.get(c)){
                hash2.set(s[st], hash2.get(s[st]) - 1);
                st++;
            }
        }
        //窗口不合法3，窗口长度超过了
        while(end - st + 1 > p.length){
            hash2.set(s[st], hash2.get(s[st]) - 1);//debug2，滑动了窗口，但是忘记处理hash2了
            st++;
        }
        if(end - st + 1 === p.length){
            res.push(st);
        }
    }
    return res;
};

不带注释版本

/**
 * @param {string} s
 * @param {string} p
 * @return {number[]}
 */
var findAnagrams = function(s, p) {
    let hash = new Map();
    let hash2 = new Map();
    let res = [];
    for(let i = 0; i < p.length; i++){
        if(hash.has(p[i])){
            hash.set(p[i], hash.get(p[i]) + 1);
        }else hash.set(p[i], 1);
    }
    let st = 0;
    for(let end = 0; end < s.length; end++){
        let c = s[end];
        if(hash2.has(c)){
            hash2.set(c, hash2.get(c) + 1);
        }else hash2.set(c, 1);
        if(!hash.has(c)){
            while(st != end + 1){
                hash2.set(s[st], hash2.get(s[st]) - 1);
                st++;
            }
        }else if(hash2.get(c) > hash.get(c)){
            while(hash2.get(c) != hash.get(c)){
                hash2.set(s[st], hash2.get(s[st]) - 1);
                st++;
            }
        }
        while(end - st + 1 > p.length){
            hash2.set(s[st], hash2.get(s[st]) - 1);
            st++;
        }
        if(end - st + 1 === p.length){
            res.push(st);
        }
    }
    return res;
};

子串

【优先二刷】和为 K 的子数组

560. 和为 K 的子数组

给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。

子数组是数组中元素的连续非空序列。

示例 1：

1 2	输入：nums = [1,1,1], k = 2 输出：2

示例 2：

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

code:

一刷本来想用滑动窗口做，但是发现有负数，没法用滑动窗口做。

这个问题可以通过使用“前缀和”加上“哈希表”来高效解决。基本思路是，我们遍历数组，计算每个位置的前缀和，即从数组开始到当前元素的累计和。然后，对于每个前缀和，我们检查是否存在一个之前的前缀和，其值等于“当前前缀和 - k”。如果存在，这意味着这两个前缀和之间的元素的和正好为k。我们使用哈希表来存储每个前缀和出现的次数，这样就可以在O(1)时间内查找到之前的前缀和。

在这道题学会了前缀和的用法，这确实是我比较少用的一个点

学习了：

前缀和的思想
用对象来构建哈希表
let of的用法，
- let of访问的是value
- let in访问的是索引号
- 如果想同时访问value和index可以用for循环或者nums.forEach((value, index) => {console.log(1);});

forEach()方法在遍历数组时访问的是原数组。这意味着在forEach()循环中，您可以直接访问并操作原数组的元素。

forEach()里面的回调函数确实可以修改原数组的元素。但是，需要注意的是，虽然您可以修改数组的元素，比如通过索引更改元素的值，您却不能通过forEach()直接修改数组的结构，例如增加或删除元素，对数组结构的修改不会影响到遍历过程。这是因为forEach()遍历的范围在第一次调用回调函数之前就已经确定了。

下面是一个示例，展示了如何通过forEach()修改原数组的元素：
1
2
3
4
5
6
7
8
9
let nums = [1, 2, 3, 4];

// 使用 forEach() 修改数组元素的值
nums.forEach((value, index, array) => {
    // 将每个元素值加倍
    array[index] = value * 2;
});

console.log(nums); // 输出: [2, 4, 6, 8]
在这个例子中，我们通过forEach()遍历数组，并将每个元素的值加倍。虽然我们在forEach()的回调函数中直接修改了数组元素的值，但是请注意，如果尝试在遍历过程中添加或删除元素，可能不会影响当前的遍历过程，因为遍历的范围是在遍历开始前就已经确定了。

由此可见，这是一个数学题TAT，思路如下：

a1 a2 a3 a4 a5 a6
cn1 = a1 + a2
cn2 = a1 + a2 + a3 + a4


//如果 a3 + a4 = k =>有一个子串和位k

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var subarraySum = function(nums, k) {
    let pre_sum_hash = {0 : 1};
    let sum = 0;
    let res = 0;
    for(let num of nums){
        sum += num;
        // sum - otherPreSum = k => sum - k = otherPreSum 
        let otherPreSum = sum - k;
        if(pre_sum_hash[otherPreSum] !== undefined){
            res += pre_sum_hash[otherPreSum];
        }
        //更新哈希表
        if(pre_sum_hash[sum] !== undefined){
            pre_sum_hash[sum]++;
        }else{
            pre_sum_hash[sum] = 1;
        }
    }
    return res;
};

leetcode热题hot100【JS】

更新时间

刷算法题可能用到的函数和表示方式

常用的表达方式

数组

字符串

Map

Set

100题实战

哈希

两数之和【数组、哈希】

字母异位词分组【数组、哈希、字符串】

【要二刷】最长连续序列【并查集、数组、哈希表】

双指针

移动零【数组、双指针】

盛最多水的容器【双指针、贪心】

【优先二刷】三数之和 【数组，双指针】

【！！dp，还没写】接雨水

滑动窗口

无重复字符的最长子串

找到字符串中所有字母异位词

子串

【优先二刷】和为 K 的子数组

【优先二刷】三数之和【数组，双指针】