hxy的博客

Mia san Mia!

0%

滑动窗口和双指针刷题

发表于 更新于 分类于 Valine：

按照算法和数据结构进行分类，一起来刷题，用于自己在面试前查漏补缺。我的意向岗位是前端，选择用javascript来刷题，优点是动态语言，语法简单，缺点是遇见复杂数据结构会出现较难的写法，如堆、并查集，每题对应leetcode的题号。本篇是滑动窗口和双指针

专题部分

滑动窗口和双指针

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

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

示例 1:

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

示例 2:

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

示例 3:

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

示例 4:

1
2
输入: s = ""
输出: 0

提示：

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

保持一个无重复窗口

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
/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function(s) {
    let window = {};

    let left = 0, right = 0;
    let res = 0; // 记录结果
    while (right < s.length) {
        let c = s[right];
        right++;
        // 进行窗口内数据的一系列更新
        if (window[c]) {
            window[c]++;
        } else {
            window[c] = 1;
        }

        // 判断左侧窗口是否要收缩
        while (window[c] > 1) {
            let d = s[left];
            left++;
            // 进行窗口内数据的一系列更新
            window[d]--;
        }
        // 在这里更新答案
        res = Math.max(res, right - left);
    }
    return res;
};

不使用滑动窗口，直接使用set存储数据

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function(s) {
    const occ = new Set();
    const len = s.length;
    let rk = -1, ans = 0;
    for (let i = 0; i < len; i++){
        if (i) {
            occ.delete(s[i - 1]);
        }
        while(rk + 1 < len && !occ.has(s[rk + 1])){
            occ.add(s[rk + 1]);
            rk++;
        }
        ans = Math.max(ans, rk - i + 1);
    }
    return ans;
};

11. 盛最多水的容器

给你 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0) 。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

说明：你不能倾斜容器。

示例 1：

img

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

示例 3：

1
2
输入：height = [4,3,2,1,4]
输出：16

示例 4：

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

提示：

  • n = height.length
  • 2 <= n <= 3 * 104
  • 0 <= height[i] <= 3 * 104

左右双指针遍历取得有可能的最大容积

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/**
 * @param {number[]} height
 * @return {number}
 */
var maxArea = function(height) {
    let left = 0, right = height.length - 1;
    let max = 0;
    while (left < right){
        max = Math.max(max, (right - left) * Math.min(height[left], height[right]));
        if (height[left] >= height[right]){
            right--;
        } else {
            left++;
        }
    }
    return max;
};

15. 三数之和

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。

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

示例 1：

1
2
输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]

示例 2：

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

示例 3：

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

提示：

  • 0 <= nums.length <= 3000
  • -105 <= nums[i] <= 105

先排序，固定最小值然后双指针找到中间值和最大值

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
/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var threeSum = function(nums) {
    const result = [];
    nums.sort((a, b) => a - b);
    for (let i = 0; i < nums.length; i++) {
        // 跳过重复数字
        if (i && nums[i] === nums[i - 1]) continue;
        let left = i + 1;
        let right = nums.length - 1;
        while (left < right) {
            const sum = nums[i] + nums[left] + nums[right];
            if (sum > 0) {
                right--;
            } else if (sum < 0) {
                left++;
            } else {
                result.push([nums[i], nums[left++], nums[right--]]);
                // 跳过重复数字
                while (nums[left] === nums[left - 1]) {
                    left++;
                }
                // 跳过重复数字
                while (nums[right] === nums[right + 1]) {
                    right--;
                }
            }
        }
    }
    return result;
};

42. 接雨水

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

示例 1：

img

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
  • 0 <= n <= 3 * 104
  • 0 <= height[i] <= 105

先不考虑空间因素，很直观的一个方法：对于下标 i，下雨后水能到达的最大高度等于下标 i 两边的最大高度的最小值，下标 i 处能接的雨水量等于下标 i 处的水能到达的最大高度减去 height[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
/**
 * @param {number[]} height
 * @return {number}
 */
var trap = function(height) {
    if (!height.length) return 0;
    let n = height.length;
    let ans = 0;
    // 数组充当备忘录
    let l_max = new Array(n), r_max = new Array(n);
    // 初始化 base case
    l_max[0] = height[0];
    r_max[n - 1] = height[n - 1];
    // 从左向右计算 l_max
    for (let i = 1; i < n; i++)
        l_max[i] = Math.max(height[i], l_max[i - 1]);
    // 从右向左计算 r_max
    for (let i = n - 2; i >= 0; i--) 
        r_max[i] = Math.max(height[i], r_max[i + 1]);
    // 计算答案
    for (let i = 1; i < n - 1; i++) 
        ans += Math.min(l_max[i], r_max[i]) - height[i];
    return ans;
};

使用双指针优化

注意到下标 i 处能接的雨水量由 leftMax[i] 和rightMax[i] 中的最小值决定。由于数组 leftMax 是从左往右计算，数组 rightMax 是从右往左计算，因此可以使用双指针和两个变量代替两个数组。

维护两个指针 left 和 right，以及两个变量 leftMax 和 rightMax，初始时 left=0,right=n−1,leftMax=0,rightMax=0。指针 left 只会向右移动，指针 right 只会向左移动，在移动指针的过程中维护两个变量 leftMax 和 rightMax 的值。

当两个指针没有相遇时，进行如下操作：

使用 height[left] 和 height[right] 的值更新 leftMax 和 rightMax 的值；

如果 height[left]<height[right]，则必有 leftMax<rightMax，下标 left 处能接的雨水量等于 leftMax−height[left]，将下标 left 处能接的雨水量加到能接的雨水总量，然后将 left 加 1（即向右移动一位）；

如果 height[left]≥height[right]，则必有 leftMax≥rightMax，下标 right 处能接的雨水量等于 rightMax−height[right]，将下标 right 处能接的雨水量加到能接的雨水总量，然后将 right 减 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
/**
 * @param {number[]} height
 * @return {number}
 */
var trap = function(height) {
    if (!height.length) return 0;
    let n = height.length;
    let left = 0, right = n - 1;
    let ans = 0;

    let l_max = height[0];
    let r_max = height[n - 1];

    while (left <= right) {
        l_max = Math.max(l_max, height[left]);
        r_max = Math.max(r_max, height[right]);

        // ans += min(l_max, r_max) - height[i]
        if (l_max < r_max) {
            ans += l_max - height[left];
            left++; 
        } else {
            ans += r_max - height[right];
            right--;
        }
    }
    return ans;
};

当然牺牲时间换取空间的方法比较好想，时间复杂度为$$O(n^2)$$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * @param {number[]} height
 * @return {number}
 */
var trap = function(height) {
    let n = height.length;
    let ans = 0;
    for (let i = 1; i < n - 1; i++) {
        let l_max = 0, r_max = 0;
        // 找右边最高的柱子
        for (let j = i; j < n; j++)
            r_max = Math.max(r_max, height[j]);
        // 找左边最高的柱子
        for (let j = i; j >= 0; j--)
            l_max = Math.max(l_max, height[j]);
        // 如果自己就是最高的话，
        // l_max == r_max == height[i]
        ans += Math.min(l_max, r_max) - height[i];
    }
    return ans;
};

76. 最小覆盖子串

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。

注意：如果 s 中存在这样的子串，我们保证它是唯一的答案。

示例 1：

1
2
输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"

示例 2：

1
2
输入：s = "a", t = "a"
输出："a"

提示：

  • 1 <= s.length, t.length <= 105
  • s 和 t 由英文字母组成

进阶：你能设计一个在 o(n) 时间内解决此问题的算法吗？

使用滑动窗口统计窗口中字符串t中各字母数量

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
53
54
55
56
57
58
59
60
/**
 * @param {string} s
 * @param {string} t
 * @return {string}
 */
var minWindow = function(s, t) {
    let need = {}, window = {};
    let needLen = 0;
    for (let c of t) {
        if (need[c]) {
            need[c]++;
        } else {
            need[c] = 1;
            needLen++;
        }
    }
    let left = 0, right = 0;
    let valid = 0;
    // 记录最小覆盖子串的起始索引及长度
    let start = 0, len = Number.MAX_SAFE_INTEGER;
    while (right < s.length) {
        // c 是将移入窗口的字符
        let c = s[right];
        // 右移窗口
        right++;
        // 进行窗口内数据的一系列更新
        if (need[c]) {
            if(window[c]) {
                window[c]++;
            } else {
                window[c] = 1;
            }
            if (window[c] === need[c]) {
                valid++;
            }
        }
        // 判断左侧窗口是否要收缩
        while(valid === needLen) {
            // 在这里更新最小覆盖子串
            if (right - left < len) {
                start = left;
                len = right - left;
            }
            // d 是将移出窗口的字符
            let d = s.charAt(left);
            // 左移窗口
            left++;
            // 进行窗口内数据的一系列更新
            if (need[d]) {
                if (window[d] === need[d]) {
                    valid--;
                }
                window[d]--;
            }
        }
        // console.log(start, len)
    }
    // 返回最小覆盖子串
    return len === Number.MAX_SAFE_INTEGER? "" : s.substring(start, start + len);
};

283. 移动零

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

示例:

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

说明:

  1. 必须在原数组上操作，不能拷贝额外的数组。
  2. 尽量减少操作次数。

双指针

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 * 双指针
 */
var moveZeroes = function(nums) {
    // 左指针指向当前非0位，右指针指向右指针
    let n = nums.length, left = 0, right = 0;
    // 未遍历完全
    while (right < n) {
        // 右指针指向的数不为0的数
        if (nums[right]) {
            // 交换左右左右指针的数
            swap(nums,left, right);
            left++;
        }
        right++;
    }
};
function swap(arr, left, right) {
    let temp = arr[left];
    arr[left] = arr[right];
    arr[right] = temp;
}

经过变化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 * 双指针变化
 */
var moveZeroes = function(nums) {
    // 非0的指针
    let index = 0;
    for (let i = 0; i < nums.length; i++) {
        // 遇到非0项
        if (nums[i] !== 0) {
            // 覆盖到index上
            nums[index] = nums[i];
            // index后移
            index++;
        }
    }
    // 剩下的位置赋为0
    for (let i = index; i < nums.length; i++) {
        nums[i] = 0;
    }
}

424. 替换后的最长重复字符

给你一个仅由大写英文字母组成的字符串，你可以将任意位置上的字符替换成另外的字符，总共可最多替换 k 次。在执行上述操作后，找到包含重复字母的最长子串的长度。

注意：字符串长度 和 k 不会超过 104。

示例 1：

1
2
3
输入：s = "ABAB", k = 2
输出：4
解释：用两个'A'替换为两个'B',反之亦然。

示例 2：

1
2
3
4
5
输入：s = "AABABBA", k = 1
输出：4
解释：
将中间的一个'A'替换为'B',字符串变为 "AABBBBA"。
子串 "BBBB" 有最长重复字母, 答案为 4。

使用滑动窗口，且统计窗口里面个数最多的元素个数

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
53
54
55
56
57
58
59
60
61
62
/**
 * @param {string} s
 * @param {number} k
 * @return {number}
 * 滑动窗口
 */
var characterReplacement = function(s, k) {
    // 1. 设置最高次数
    let maxTime = 0;

    // 2. 遍历字符串
    for (let i = 0; i < s.length; i++) {
        // 2.1 设置窗口起点值
        const value = s[i];
        
        // 2.2 设置参数
        let replaceTime = k, // 可滑动次数
        slide = i, // 滑动的下标
        time = 1; // 本次出现数
        
        // 2.3 向右开始滑动
        while (
            (replaceTime || s[slide + 1] === value) // 还有滑动次数或者下一个字符串相同
            && slide < s.length - 1 // 限制滑动边界 [i, s.length - 1]
        ) {
            // 每滑动一次向右移一位
            slide++;
            // 每滑动一次本次出现数 + 1
            time++;
            // 如果本次是不相同的，减少滑动次数
            if (s[slide] !== value) {
                replaceTime--;
            }
        }

        // 2.4 如果向右到顶，但是还有 replaceTime，
        // 表明向左还可以滑，那就继续向左滑动
        // 滑动前重置一下开始位置
        slide = i;
        
        // 2.5 向左开始滑动
        while (
            (replaceTime || s[slide - 1] === value) // 类似向右的判断
            && slide > 0 // 边界为 [0, i]
        ) {
            // 每滑动一次向左移一位
            slide--;
            // 每滑动一次本次出现数 + 1
            time++;
            // 如果本次是不相同的，减少滑动次数
            if (s[slide] !== value) {
                replaceTime--;
            }
        }

        // 2.6 将本次滑动次数汇总到最高次数中
        maxTime = Math.max(maxTime, time);
    }

    // 3. 返回结果
    return maxTime;
};

用一个数组保存滑动窗口内各字母的个数，方便比较当前最多的字母个数

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
/**
 * @param {string} s
 * @param {number} k
 * @return {number}
 * 双指针
 */
var characterReplacement = function(s, k) {
    // 长度
    const n = s.length;
    // 数组
    const num = Array(26).fill(0);
    let maxn = 0;
    // 左右指针
    let left = 0, right = 0; 

    while (right < n) {
        // 统计右指针对应的字母的个数
        num[s[right].charCodeAt() - 'A'.charCodeAt()]++;
        // 比较当前最长长度和现在的最长长度
        maxn = Math.max(maxn, num[s[right].charCodeAt() - 'A'.charCodeAt()]);
        // c窗口内除了出现次数最多的那一类字符之外，剩余的字符数量不超过 k个
        if (right - left + 1 - maxn > k) {
            num[s[left].charCodeAt() - 'A'.charCodeAt()]--;
            // 左指针移动
            left++;
        }
        right++;
    }
    return right - left;
};

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

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

异位词 指字母相同，但排列不同的字符串。

示例 1:

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

示例 2:

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

提示:

  • 1 <= s.length, p.length <= 3 * 104
  • s 和 p 仅包含小写字母

滑动窗口

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
53
54
55
56
57
58
/**
 * @param {string} s
 * @param {string} p
 * @return {number[]}
 */
var findAnagrams = function(s, p) {
    let need = {}, window = {};
    let needLen = 0;
    for (let c of p) {
        if (need[c]) {
            need[c]++;
        } else {
            need[c] = 1;
            needLen++;
        }
    }
    let res = [];
    let left = 0, right = 0;
    let valid = 0;
    while (right < s.length) {
        // c 是将移入窗口的字符
        let c = s[right];
        // 右移窗口
        right++;
        // 进行窗口内数据的一系列更新
        if (need[c]) {
            if(window[c]) {
                window[c]++;
            } else {
                window[c] = 1;
            }
            if (window[c] === need[c]) {
                valid++;
            }
        }

        // 判断左侧窗口是否要收缩
        while(right - left >= p.length) {
            // 在这里判断是否找到了合法的子串
            if (valid === needLen) {
                res.push(left);
            }
            // d 是将移出窗口的字符
            let d = s[left];
            // 左移窗口
            left++;
            // 进行窗口内数据的一系列更新
            if (need[d]) {
                if (window[d] == need[d]) {
                    valid--;
                }
                window[d]--;
            }
        }
    }
    // 未找到符合条件的子串
    return res;
};

1004. 最大连续1的个数 III

给定一个由若干 0 和 1 组成的数组 A，我们最多可以将 K 个值从 0 变成 1 。

返回仅包含 1 的最长（连续）子数组的长度。

示例 1：

1
2
3
4
5
输入：A = [1,1,1,0,0,0,1,1,1,1,0], K = 2
输出：6
解释： 
[1,1,1,0,0,1,1,1,1,1,1]
粗体数字从 0 翻转到 1，最长的子数组长度为 6。

示例 2：

1
2
3
4
5
输入：A = [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], K = 3
输出：10
解释：
[0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,1,1,1,1]
粗体数字从 0 翻转到 1，最长的子数组长度为 10。

提示：

  1. 1 <= A.length <= 20000
  2. 0 <= K <= A.length
  3. A[i] 为 0 或 1

面试时候没想起来滑动窗口，结果写了一版动态规划，其实很简单，记录滑动窗口里面的0，小于k个即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 * @param {number[]} A
 * @param {number} K
 * @return {number}
 * 滑动窗口
 */
var longestOnes = function(A, K) {
    // 最终结果
    let res = 0;
    // 滑动窗口内0的个数
    let zeros = 0;
    // 左指针
    let left = 0;
    // 右指针
    for (let right = 0; right < A.length; right++) {
        // 0的个数
        if (A[right] === 0) zeros++;
        while (zeros > K) {
            if (A[left++] === 0) --zeros;
        }
        res = Math.max(res, right - left + 1);
    }
    return res;
};
-------------本文结束感谢您的阅读-------------

欢迎关注我的其它发布渠道