【LeetCode与《代码随想录》】数组篇：做题笔记与总结-JavaScript版

感觉关于JavaScript的题解不太多，所以就写一个，给自己总结用。

代码随想录

https://www.programmercarl.com/

主要题目

704. 二分查找（二分）

704. 二分查找

• 经典二分
• 注意，取中点要用>>位运算移动，因为直接/2会产生小数
• 这里的范围是左闭右闭，因此如果在循环中mid取不到答案的话，left和right的更新分别是mid+1和mid-1
• 对上句话的解释：如果在mid取不到的情况下还更新为mid，那范围就是开（左闭右开/左开右闭）
• 关于范围：题目中说n的范围是10000。而js中let是Number，是64位的，不会爆。
• 若是会爆：left+(right-left)>>1

var search = function(nums, target) {
    let left=0,right=nums.length-1;
    let mid=(left+right)>>1;
    while(left<=right){
        if(nums[mid]===target){
            return mid;
        }else{
            if(nums[mid]<target){
                left=mid+1;
            }else{
                right=mid-1;
            }
        }
        mid=(left+right)>>1;
    }
    return -1;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

27. 移除元素（双指针）

27. 移除元素

• 双指针：i是快指针，遍历数组；j是慢指针，填入答案
• i一定比j快（或等于）
• j是下标，但返回的是数组长度，数组的答案部分是[0,j-1]，长度为j

var removeElement = function(nums, val) {
    // i>=j
    let i=0,j=0;
    for(;i<nums.length;i++){
        if(nums[i]!=val){
            nums[j++]=nums[i];         
        }
    }
    return j;
};
1
2
3
4
5
6
7
8
9
10

977. 有序数组的平方（双指针）

977. 有序数组的平方

• 双指针
• 非递减：递增有相同
• 若是全正或全负，数组的平方是单调的
• 若有正有负，数组的平方是点减后增：两端大，中间小
• 双指针ij，一头一尾，大的进答案

var sortedSquares = function(nums) {
    // 非递减:递增有相同
    let n=nums.length;
    let ans=new Array(n).fill(0);
    for(let i=0,j=n-1,k=n-1;i<=j;k--){
        let ii=nums[i]*nums[i];
        let jj=nums[j]*nums[j];
        if(ii>=jj){
            ans[k]=ii;i++;
        }else{
            ans[k]=jj;j--;
        }
    }
    return ans;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

简化代码：

var sortedSquares = function(nums) {
    // 平方后，两边大，中间小，涵盖所有情况
    let i=0,j=nums.length-1;
    let ans=new Array()
    while(i<=j){
        if(nums[i]**2>=nums[j]**2){
            ans.push(nums[i++]**2);
        }else{
            ans.push(nums[j--]**2);
        }
    }
    return ans.reverse()
};
1
2
3
4
5
6
7
8
9
10
11
12
13

209. 长度最小的子数组（滑动窗口）

209. 长度最小的子数组

• 双指针：滑动窗口
• 窗口为从l到r
• 但凡当前sum>=target，保存ans=min(ans,当前长度）（于是会保存所有长度的最小长度），然后另l++
• 若sum=target的条件）

var minSubArrayLen = function(target, nums) {
    const n=nums.length;
    let l=0,r=0,sum=0,ans=n+1;
    while(r<n){
        sum+=nums[r++];
        while(sum>=target){
            // 让窗口变小:左闭右开
            if(r-l<ans) ans=r-l;
            sum-=nums[l++];
        }
    }
    if(ans===n+1) ans=0;
    return ans;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14

或：相当于把上述代码中，窗口缩小的步骤拆出来。更直观，但代码没有上述的简洁。

var minSubArrayLen = function(target, nums) {
    let i=0,j=0;
    let sum=nums[0],ans=100001;
    while(i<nums.length&&j<nums.length){
        if(sum>=target){
            ans=Math.min(ans,j-i+1);
            if(i<j){
                i++;sum-=nums[i-1];
            }else if(i==j){
                // 最优的答案
                return 1;
            }
        }else{
            j++;sum+=nums[j];
        }
    }
    return ans===100001?0:ans;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

59.螺旋矩阵II（模拟）

59.螺旋矩阵II

var generateMatrix = function (n) {
    // 二维数组
    let ans = new Array(n).fill(0).map(() => new Array(n).fill(0));
    let x = 0, y = -1;
    let now = 1;

    while (now <= n * n) {
        // 右
        while (y + 1 < n && ans[x][y + 1] === 0) {
            ans[x][y + 1] = now++;
            y++;
        }
        if (now > n * n) break;
        // 下
        while (x + 1 < n && ans[x + 1][y] === 0) {
            ans[x + 1][y] = now++;
            x++;
        }
        if (now > n * n) break;
        // 左
        while (y - 1 >= 0 && ans[x][y - 1] === 0) {
            ans[x][y - 1] = now++;
            y--;
        }
        if (now > n * n) break;
        // 上
        while (x - 1 >= 0 && ans[x - 1][y] === 0) {
            ans[x - 1][y] = now++;
            x--;
        }
    }
    return ans;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

相关题目推荐

都是和“主要题目”相似的题目。

35. 搜索插入位置（二分）

35. 搜索插入位置

• 二分
• 要先判断范围：最大与最小：目标值不在数组中
• 这里是左闭右闭，所以while循环条件为i<=j
• 若没有找到，则一定是i++到了j的位置或j- -到了i
• 即：没找到之前一定ij重叠
• 若目标值大于ij所指向的值，则i=mid+1，即：j i，此时跳出循环，i为答案
• 若小于：不可能存在这种情况，原因：
• 除法会向下取整，且题目说明数组无重复
• 如：在[1 3]中找2，mid指向的会是1，而不会是2
• 又如：在[0 1]、[3 4]中找2，显然我们在找2时不会找到这样的区间
• ps：若强行存在目标值小于ij重叠所指向的值，只可能是在数组范围外（即目标值是最小值）
• 省流：
• 先判断目标值大小是否在数组区间中
• 判断目标值是否在数组中存在，若存在可以直接二分找到
• 否则：ij一定会重叠，由于目标值大小在数组区间中，即：ij 目标值，此时i++，跳出循环，为答案

var searchInsert = function(nums, target) {
    let n=nums.length-1;
    if(target>nums[n]){
        return n+1;
    }
    if(target<nums[0]){
        return 0;
    }

    let i=0,j=n;
    let mid=(i+j)>>1;
    while(i<=j){
        if(nums[mid]===target){
            return mid;
        }
        if(nums[mid]>target){
            j=mid-1;
        }else{
            i=mid+1;
        }
        mid=(i+j)>>1;
    }
    // 走到这里说明没有且i>j
    return i;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

二刷：

var searchInsert = function(nums, target) {
    // 返回第一个>=target的值
    let l=0,r=nums.length-1;
    
    // 特判
    if(target<nums[l]) return l;
    if(target>nums[r]) return r+1;

    let mid;
    while(l<=r){
        mid=(l+r)>>1;
        if(nums[mid]===target){
            return mid;
        }
        else{
            if(nums[mid]<target){
                l=mid+1;
            }else{
                r=mid-1;
            }
        }
    }
    return l;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

34. 在排序数组中查找元素的第一个和最后一个位置（二分）

34. 在排序数组中查找元素的第一个和最后一个位置

一道细节比较多的题：

• 二分
• 分类讨论：target在数组区间范围外；target在数组区间范围内（target在数组中，target不在数组中）
• 若存在：
• 想要找到target的第一个位置和最后一个位置：相当于找到最后一个小于target和第一个大于target的位置（也可以直接找，不需要+1-1，在本题末尾）
• 最后一个小于target的位置：
• 第一个target位置-1
• 想象：一个数组，分为小于target和大于等于target的，则第一个等于target的位置-1就是最后一个小于目标的位置
• 满足>=每次都会更新，最后留下来的一定是第一个等于的-1
• 第一个大于target的位置：同理
• 每一次<=都会更新，最后留下来的是最后一个=target的位置+1

分别对应getLeft和getRight。

注意：

target是否在范围内

• 要初始化一个值来验证target是否在范围内
• 此值要小于等于-2
• 因为-1可能是有mid为0，ans更新为mid-1得到
• 左右边界但凡有一个ans为-2则表示target不在范围内

target是否存在

• 如[1 3]中找2，left指向1，right指向3，right-left=1
• 若right-left>1则存在，否则不存在

getLeft：

const getLeft=function(nums,target){
    let l=0,r=nums.length-1;
    let mid=(l+r)>>1;
    let ans=-2;
    while(l<=r){
        mid=(l+r)>>1;
        if(nums[mid]>=target){
            r=mid-1;
            // 大于等于都要变，留下的是最右边的小于
            ans=r;
        }else{
            l=mid+1;
        }
    }
    return ans;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

getRight：

// 找右边界：第一个大于target的
const getRight=function(nums,target){
    let l=0,r=nums.length-1;
    let mid=(l+r)>>1;
    let ans=-2;
    while(l<=r){
        mid=(l+r)>>1;
        if(nums[mid]>target){
            r=mid-1;
        }else{
            l=mid+1;
            // 小于等于都要变,最后留下的是最左边的大于
            ans=l;
        }
    }
    return ans;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

总体代码：

var searchRange = function(nums, target) {
    // 找左边界:最后一个小于target的
    const getLeft=function(nums,target){
        let l=0,r=nums.length-1;
        let mid=(l+r)>>1;
        let ans=-2;
        while(l<=r){
            mid=(l+r)>>1;
            if(nums[mid]>=target){
                r=mid-1;
                // 大于等于都要变，留下的是最右边的小于
                ans=r;
            }else{
                l=mid+1;
            }
        }
        return ans;
    }

    // 找右边界：第一个大于target的
    const getRight=function(nums,target){
        let l=0,r=nums.length-1;
        let mid=(l+r)>>1;
        let ans=-2;
        while(l<=r){
            mid=(l+r)>>1;
            if(nums[mid]>target){
                r=mid-1;
            }else{
                l=mid+1;
                // 小于等于都要变,最后留下的是最左边的大于
                ans=l;
            }
        }
        return ans;
    }

    let left=getLeft(nums,target);
    let right=getRight(nums,target);
    
    // 范围外
    if(left===-2||right===-2){
        return [-1,-1]
    }
    // 存在
    if(right-left>1) {
        return[left+1,right-1];
    }
    // 不存在
    return [-1,-1]
    
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

直接找第一个和最后一个target也可以：但感觉上面的方法边界的差异感强一些，更好理解。

var searchRange = function(nums, target) {
    // 找左边界:最后一个小于target的
    const getLeft=function(nums,target){
        let l=0,r=nums.length-1;
        let mid=(l+r)>>1;
        let ans=-2;
        while(l<=r){
            mid=(l+r)>>1;
            if(nums[mid]>=target){
                r=mid-1;
                // 大于等于都要变，留下的是第一个target
                ans=r+1;
            }else{
                l=mid+1;
            }
        }
        return ans;
    }

    // 找右边界：第一个大于target的
    const getRight=function(nums,target){
        let l=0,r=nums.length-1;
        let mid=(l+r)>>1;
        let ans=-2;
        while(l<=r){
            mid=(l+r)>>1;
            if(nums[mid]>target){
                r=mid-1;
            }else{
                l=mid+1;
                // 小于等于都要变,最后留下的是最后一个target
                ans=l-1;
            }
        }
        return ans;
    }

    let left=getLeft(nums,target);
    let right=getRight(nums,target);
    console.log(left,right)
    // 范围外
    if(left===-2||right===-2){
        return [-1,-1]
    }
    // 存在
    if(right-left>=0) {
        return[left,right];
    }
    // 不存在
    return [-1,-1]
    
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

另一种更简单的判断是否存在的方式：

 if(nums[l]===target) return [l,r];
    else return [-1,-1];
1
2

总体：

var searchRange = function(nums, target) {

    var getLeft=function(nums,target){
        let l=0,r=nums.length-1;
        let mid,ans;
        while(l<=r){
            mid=(l+r)>>1;
            if(nums[mid]>=target){
                r=mid-1;
                // 每次遇到>=target时都更新ans为mid-1
                // 则最后一个ans为第一个target-1
                ans=r;
            }else{
                l++;
            }
        }
        return ans;
    }

    var getRight=function(nums,target){
        let l=0,r=nums.length-1;
        let mid,ans;
        while(l<=r){
            mid=(l+r)>>1;
            if(nums[mid]<=target){
                l=mid+1;
                ans=l;
            }else{
                r--;
            }
        }
        return ans;
    }

    let l=getLeft(nums,target)+1;
    let r=getRight(nums,target)-1;
    if(nums[l]===target) return [l,r];
    else return [-1,-1];    
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

69. x 的平方根 （二分）

69. x 的平方根

• 要求算术平方根，且去掉小数
• 其实就是答案向下取整，即：
• mid x mid<=x都要存在ans中，最后一次ans的赋值一定是 平方等于x的数 或 刚好小于x的数

var mySqrt = function(x) {
    let l=0,r=47000;
    let ans,mid;
    while(l<=r){
        mid=(l+r)>>1;
        // 小于等于都要存,最后保存的是最近的小于或直接等于
        if(mid*mid<=x){
            ans=mid;
            l=mid+1;
        }else {
            r=mid-1;
        }
    }
    return ans;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

367. 有效的完全平方数（重复）

367. 有效的完全平方数

• 跟上一题一样

var isPerfectSquare = function(num) {
    let l=0,r=47000;
    let mid,ans;
    while(l<=r){
        mid=(l+r)>>1;
        if(mid*mid<=num){
            ans=mid;
            l=mid+1;
        }else{
            r=mid-1;
        }
    }
    if(ans*ans===num) return true;
    else return false;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

26. 删除有序数组中的重复项（双指针）

https://leetcode.cn/problems/remove-duplicates-from-sorted-array/

• 双指针

var removeDuplicates = function(nums) {
    let n=nums.length-1;
    let i=1,j=0;
    for(;i<=n;i++){
        if(nums[i]!=nums[j]){
            nums[++j]=nums[i];
        }
    }
    return j+1;
};
1
2
3
4
5
6
7
8
9
10

283. 移动零（双指针）

283. 移动零

• 双指针

var moveZeroes = function(nums) {
    let n=nums.length-1;
    let i=0,j=0;
    for(;i<=n;i++){
        if(nums[i]){
            nums[j++]=nums[i];
        }
    }
    for(;j<=n;j++){
        nums[j]=0;
    }
    return nums;
};
1
2
3
4
5
6
7
8
9
10
11
12
13

844. 比较含退格的字符串（模拟）

844. 比较含退格的字符串

• 模拟
• cnt表示要还有多少#

var backspaceCompare = function(s, t) {
    let ss='',tt='';
    let cnt=0;
    for(let i=s.length-1;i>=0;i--){
        if(cnt){
            if(s[i]==='#'){
                cnt++;
            }else{
                cnt--;
            }
        }else{
            if(s[i]==='#'){
                cnt++;
            }else{
                ss+=s[i];
            }
        }
    }
    cnt=0;
    for(let i=t.length-1;i>=0;i--){
        if(cnt){
            if(t[i]==='#'){
                cnt++;
            }else{
                cnt--;
            }
        }else{
            if(t[i]==='#'){
                cnt++;
            }else{
                tt+=t[i];
            }
        }
    }
    // console.log(ss,tt)
    if(ss===tt) return true;
    else return false;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

简化代码：

var backspaceCompare = function(s, t) {
    let ss='',cnt=0;
    for(let i=s.length-1;i>=0;i--){
        if(s[i]==='#') cnt++;
        else{
            if(cnt) cnt--;
            else ss+=s[i];
        }
    }

    let tt='';cnt=0;
    for(let i=t.length-1;i>=0;i--){
       if(t[i]==='#') cnt++;
        else{
            if(cnt) cnt--;
            else tt+=t[i];
        }
    }

    if(ss===tt) return true;
    else return false;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

904. 水果成篮（滑动窗口）

904. 水果成篮

• 滑动窗口
• 跟209很像，加上了Map的运用
• Map要记录出现的次数，而不是简单的是否出现过，原因看样例：[0,1,6,6,4,4,6]

var totalFruit = function(fruits) {
    let n=fruits.length,ans=0;
    // 要用map记录数量，而不只是是否存在
    let map=new Map();
    let l=0,r=0;
    for(r=0;r<n;r++){
        map.set(fruits[r],(map.get(fruits[r])||0)+1);

        while(map.size>2){
            map.set(fruits[l],map.get(fruits[l])-1);
            if(map.get(fruits[l])===0){
                map.delete(fruits[l]);
            }
            l++;
        }

        ans=Math.max(ans,r-l+1)
    }
    return ans;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

写过一个错误的代码，它在缩小滑动窗口时使用的是if(map.size>2)，但是它能通过所有的样例。

经过一番思考发现，if判断会使得每次r++时有l++，也就是说，此时的map大小不变。因此不会对最后的ans有影响（题目所求的是ans的最大值）。但是这样的话map将不会只有2种水果。
在此代码中，想要让ans继续变大，只有在每次r++时map.size<=2才行，这样才不会l++。

举个例子，样例[1,2,1,3,3].

[1,2,1] 时，有最大数量，3
遇到3时，l++，此时篮子里是[2,1,3]。
篮子里有3种水果，但r-l+1 还是3
（当然，这里应该是2，不过这里是3不会影响最后的结果）

var totalFruit = function(fruits) {
    const n=fruits.length;
    const map=new Map();
    let l=0,r=0,ans=0;
    for(;r<n;r++){
        // 放新的
        map.set(fruits[r],(map.get(fruits[r])||0)+1);

        if(map.size>2){
            map.set(fruits[l],map.get(fruits[l])-1);
            if(map.get(fruits[l])===0){
                map.delete(fruits[l])
            }
            l++;          
        }

        ans=Math.max(ans,r-l+1);
        
    }
    return ans;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

76. 最小覆盖子串（滑动窗口）

76. 最小覆盖子串

54. 螺旋矩阵（模拟）

注意：这里跳出循环的条件与59不同。

这里是获取数字，因此cnt从0开始，每获取一个就+1，当获取到n*m个是结束。
59是填入数字，因此cnt从1开始填，填完就+1，当cnt>n*m时说明第n*m个刚好填完，跳出循环。

var spiralOrder = function (matrix) {
    let ans = new Array()
    let i = 0, j = -1, cnt = 0, sum = matrix.length * matrix[0].length;
    while (cnt < sum) {
        // 右
        while (j + 1 < matrix[0].length && matrix[i][j + 1] != 101) {
            ans.push(matrix[i][j + 1])
            matrix[i][j + 1] = 101
            j++; cnt++;
        }
        if (cnt >= sum) break;

        // 下
        while (i + 1 < matrix.length && matrix[i + 1][j] != 101) {
            ans.push(matrix[i + 1][j])
            matrix[i + 1][j] = 101
            i++; cnt++;
        }
        if (cnt >= sum) break;

        // 左
        while (j - 1 >= 0 && matrix[i][j - 1] != 101) {
            ans.push(matrix[i][j - 1])
            matrix[i][j - 1] = 101
            j--; cnt++;
        }
        if (cnt >= sum) break;

        // 上
        while (i - 1 >= 0 && matrix[i - 1][j] != 101) {
            ans.push(matrix[i - 1][j])
            matrix[i - 1][j] = 101
            i--; cnt++;
        }
    }

    return ans;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38