Sliding Window

滑动窗口主要解决满足某个条件的连续子串问题，因为我们枚举 区间、子数组、子串问题的时候时间复杂度是\(O(n^2)\)，使用滑窗可以将时间复杂度优化至\(O(n)\)。

优质题解

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

  1. left = Math.max(left , map.get(s.charAt(i))+1);十分tricky，举例 abba
  2. 当遍历到第二个a的时候，此时的left指向第二个b，right指向第二个a，字符出现重复，所以要更新left，往map里一查，之前出现的a下标比left还小，说明当前记录的最长不重复子串就不包含第一个a，所以left不变
  3. 然后不管出没出现重复字符，都要执行 map.put(s.charAt(i) , i);如果字符串是abbab，当遍历到最后一个b的时候，left赋值为第二个b 的下标 + 1 的位置，也就是a下标的位置；如果出现重复字符就不执行map.put(s.charAt(i) , i)，那么此时b在map里记录的下标是第一个b的下标
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
public int lengthOfLongestSubstring(String s) {
        HashMap<Character, Integer> map = new HashMap<>();
        int maxLen = 0;//用于记录最大不重复子串的长度
        int left = 0;//滑动窗口左指针
        for (int i = 0; i < s.length() ; i++)
        {
            /**
            1、首先，判断当前字符是否包含在map中，如果不包含，将该字符添加到map（字符，字符在数组下标）,
             此时没有出现重复的字符，左指针不需要变化。此时不重复子串的长度为：i-left+1，与原来的maxLen比较，取最大值；

            2、如果当前字符 ch 包含在 map中，此时有2类情况：
             1）当前字符包含在当前有效的子段中，如：abca，当我们遍历到第二个a，当前有效最长子段是 abc，我们又遍历到a，
             那么此时更新 left 为 map.get(a)+1=1，当前有效子段更新为 bca；
             2）当前字符不包含在当前最长有效子段中，如：abba，我们先添加a,b进map，此时left=0，我们再添加b，发现map中包含b，
             而且b包含在最长有效子段中，就是1）的情况，我们更新 left=map.get(b)+1=2，此时子段更新为 b，而且map中仍然包含a，map.get(a)=0；
             随后，我们遍历到a，发现a包含在map中，且map.get(a)=0，如果我们像1）一样处理，就会发现 left=map.get(a)+1=1，实际上，left此时
             应该不变，left始终为2，子段变成 ba才对。

             为了处理以上2类情况，我们每次更新left，left=Math.max(left , map.get(ch)+1).
             另外，更新left后，不管原来的 s.charAt(i) 是否在最长子段中，我们都要将 s.charAt(i) 的位置更新为当前的i，
             因此此时新的 s.charAt(i) 已经进入到 当前最长的子段中！
             */
            if(map.containsKey(s.charAt(i)))
            {
                left = Math.max(left , map.get(s.charAt(i))+1);
            }
            //不管是否更新left，都要更新 s.charAt(i) 的位置！
            map.put(s.charAt(i) , i);
            maxLen = Math.max(maxLen , i-left+1);
        }
        
        return maxLen;
    }

30. 串联所有单词的子串

"ling mind rabo ofoo owin gdin gbar rwin g monkeypoundcake" ["fooo","barr","wing","ding","wing"]

187. 重复的DNA序列

方法一：暴搜(说是滑动窗口也行吧)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public List<String> findRepeatedDnaSequences(String s) {
        List<String> res = new LinkedList<>();
        Map<String, Integer> map = new HashMap<>();
        for (int l = 0; l <= s.length() - 10; ++l) {
            String subStr = s.substring(l, l + 10);
            map.put(subStr, map.getOrDefault(subStr, 0) + 1);
        }
        for (Map.Entry<String, Integer> entry : map.entrySet()) 
            if (entry.getValue() > 1)
                res.add(entry.getKey());
        return res;
    }
}

一次循环也可

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public List<String> findRepeatedDnaSequences(String s) {
        List<String> res = new LinkedList<>();
        Map<String, Integer> map = new HashMap<>();
        for (int l = 0; l <= s.length() - 10; ++l) {
            String subStr = s.substring(l, l + 10);
            map.put(subStr, map.getOrDefault(subStr, 0) + 1);
            if (map.getOrDefault(subStr, 0) == 2)
                res.add(subStr);
        }
        return res;
    }
}

76. 最小覆盖子串

方法一：滑动窗口(超时check部分)

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
class Solution {
    public String minWindow(String s, String t) {
        String res = "";
        if (s.length() < t.length())
            return res;
        int minLen = 100000;
        int[] map = new int[256];
        for (char ch : t.toCharArray())
            ++map[ch - 'A'];
        for (int left = 0, i = 0; i < s.length(); ++i) {
            char ch = s.charAt(i);
            --map[ch - 'A'];
            while (i - left + 1 >= t.length() && check(map, t)) {
                if (i - left + 1 < minLen) {
                    res = s.substring(left, i + 1);
                    minLen = i - left + 1;
                }
                ++map[s.charAt(left) - 'A'];
                ++left;
            }
        }
        return res;
    }

    private boolean check(int[] map, String t) {
        for (char ch : t.toCharArray())
            if (map[ch - 'A'] > 0)
                return false;
        return true;
    }
}

把t提前转换好勉强能过，char[] arr = t.toCharArray();

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
class Solution {
    public String minWindow(String s, String t) {
        String res = "";
        if (s.length() < t.length())
            return res;
        char[] arr = t.toCharArray();
        int minLen = 100000;
        int[] map = new int[128];
        for (char ch : arr)
            ++map[ch - 'A'];
        for (int left = 0, i = 0; i < s.length(); ++i) {
            char ch = s.charAt(i);
            --map[ch - 'A'];
            while (i - left + 1 >= t.length() && check(map, arr)) {
                if (i - left + 1 < minLen) {
                    res = s.substring(left, i + 1);
                    minLen = i - left + 1;
                }
                ++map[s.charAt(left) - 'A'];
                ++left;
            }
        }
        return res;
    }

    private boolean check(int[] map, char[] arr) {
        for (char ch : arr)
            if (map[ch - 'A'] > 0)
                return false;
        return true;
    }
}

209. 长度最小的子数组

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int sum = 0, minLen = 100001;
        for (int left = 0, right = 0; right < nums.length; ++right) {
            sum += nums[right];
            while (sum >= target) {
                minLen = Math.min(minLen, right - left + 1);
                sum -= nums[left++];
            }
        }
        return minLen == 100001 ? 0 : minLen;
    }
}

567. 字符串的排列

方法一：滑动窗口

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public boolean checkInclusion(String s1, String s2) {
        int[] map = new int[26];
        for (char ch : s1.toCharArray())
            ++map[ch - 'a'];
        for (int left = 0, right = 0; right < s2.length(); ++right) {
            --map[s2.charAt(right) - 'a'];
            if (right - left + 1 >= s1.length()) {
                if (check(map, s1))
                    return true;
                ++map[s2.charAt(left++) - 'a'];
            }
        }
        return false;
    }

    private boolean check(int[] map, String s) {
        for (char ch : s.toCharArray()) 
            if (map[ch - 'a'] != 0)
                return false;
        return true;
    }
    
}

1208. 尽可能使字符串相等

方法一：滑动窗口

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public int equalSubstring(String s, String t, int maxCost) {
        int maxLen = 0, cost = 0;
        for (int left = 0, i = 0; i < s.length() && i < t.length(); ++i) {
            cost += Math.abs(s.charAt(i) - t.charAt(i));
            while (left <= i && cost > maxCost) 
                cost -= Math.abs(Math.abs(s.charAt(left) - t.charAt(left++)));
            maxLen = Math.max(maxLen, i - left + 1);            
        }
        return maxLen;
    }
}

找出最长等值子数组

方法一：滑动窗口 同向双指针

  1. 将每个值的下标存到List中，例如对于nums = [1,3,2,3,1,3], k = 3

    list[1]: [0, 4]

    list[2] : [4]

    list[3]: [1, 3, 5]

  2. 枚举每个list，即把元素替换成1或2或3，例如枚举list[3]: [1, 3, 5]，l = 0, r = 1时，nums数组有list.get(r) - list.get(0) + 1 = 3 - 1 + 1 = 3个数：[3，2，3]，这个子数组中有r - l + 1 = 1 - 0 + 1 = 2个3，所以需要删除3 - 2 = 1个数

  3. 当需要删除的数大于k时，将左端点右移，直到满足需要删除的元素小于等于k

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int longestEqualSubarray(List<Integer> nums, int k) {
        int n = nums.size();
        List<Integer>[] pos = new List[n + 1];
        Arrays.setAll(pos, e -> new ArrayList<>());
        for (int i = 0; i < n; ++i)
            pos[nums.get(i)].add(i);
        int res = 0;
        for (List<Integer> list : pos) {
            int l = 0;
            for (int r = 0; r < list.size(); ++r) {
                while (list.get(r) - list.get(l) + 1 - (r - l + 1) > k)
                    ++l;
                res = Math.max(res, r - l + 1);
            }
        }
        return res;
    }
}

713. 乘积小于 K 的子数组

方法一：滑动窗口 相向双指针

res += i - l + 1;把当前[l,r]的子数组都涵括了

如果[l,r]满足条件，那么[l + 1, r], [l + 2, r], ... , [r, r]都满足，满足条件的个数为 r - l + 1

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public int numSubarrayProductLessThanK(int[] nums, int k) {
        int n = nums.length ,res = 0, l = 0, prod = 1;
        for (int i = 0; i < n; ++i) {
            prod *= nums[i];
            while (l <= i && prod >= k)
                prod /= nums[l++];
            res += i - l + 1;
        }
        return res;
    }
}

1004. 最大连续1的个数 III

方法一：滑动窗口(同向双指针)

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int longestOnes(int[] nums, int k) {
        int n = nums.length, left = 0, res = 0, cnt0 = 0;
        for (int i = 0; i < n; ++i) {
            cnt0 += 1 - nums[i];
            while (cnt0 > k) {
              cnt0 -= (nums[left++] == 0 ? 1 : 0);
            }
            res = Math.max(res, i - left + 1);
        }
        return res;
    }
}

1234. 替换子串得到平衡字符串

方法一：滑动窗口(同向双指针)

将[l,r]的字符数量减去，如果满足QWERd的数量都小于n / 4，那么子串长度为r - l + 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
class Solution {
    public int balancedString(String s) {
        int[] cnt = new int['X']; // 'X' - 'W' = 1
        int n = s.length(), l = 0, res = Integer.MAX_VALUE, target = n / 4;
        for (int i = 0; i < n; ++i)
            cnt[s.charAt(i)]++;
        if (check(cnt, target))
            return 0;
        for (int i = 0; i < n; ++i) {
            char ch = s.charAt(i);
            --cnt[ch];
            while (check(cnt, target)) {
                ++cnt[s.charAt(l)];
                res = Math.min(res, i - l + 1);
                ++l;
            }
        }
        return res;
    }

    private boolean check(int[] cnt,  int target) {
        return cnt['Q'] <= target && cnt['W'] <= target && cnt['E'] <= target && cnt['R'] <= target;
    }
}

1658. 将 x 减到 0 的最小操作数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int minOperations(int[] nums, int x) {
        int n  = nums.length, res = -1, l = 0, sum = 0;
        for (int a : nums)
            sum += a;
        int target = sum - x, cur = 0;
        if (target < 0)
            return -1;
        for (int i = 0; i < n; ++i) {
            cur += nums[i];
            while (cur > target)
                cur -= nums[l++];
            if (cur == target)
                res = Math.max(res, i - l + 1);
        }
        return res < 0 ? -1 : n - res;
    }
}

两个线段获得的最多奖品

方法一：同向双指针

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int maximizeWin(int[] pos, int k) {
        int n = pos.length, res = 0, l = 0;
        int[] pre = new int[n + 1];
        for (int i = 0; i < n; ++i) {
            while (pos[i] - pos[l] > k)
                ++l;
            res = Math.max(res, pre[l] + i - l + 1);
            pre[i + 1] = Math.max(pre[i], i - l + 1);
        }
        return res;
    }
}

1456. 定长子串中元音的最大数目

方法一：滑动窗口(同向双指针)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public int maxVowels(String s, int k) {
        Set<Character> set = new HashSet<>();
        set.add('a');
        set.add('e');
        set.add('i');
        set.add('o');
        set.add('u');
        int n = s.length(), l = 0, res = 0, cnt = 0;
        for (int i = 0; i < n; ++i) {
            char ch = s.charAt(i);
            if (set.contains(ch)) {
                ++cnt;
                res = Math.max(res, cnt);
            }
            if (i - l + 1 == k) {
                if (set.contains(s.charAt(l)))
                    --cnt;
                ++l;
            }
        }
        return res;
    }
}

2269. 找到一个数字的 K 美丽值

方法一：滑动窗口(同向双指针)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int divisorSubstrings(int num, int k) {
        String s = num + "";
        int n = s.length(), cnt = 0, x = 0, mod = (int) Math.pow(10, k - 1);
        for (int i = 0; i < k; ++i) 
            x = x * 10 + (s.charAt(i) - '0');
        for (int i = k; i < n; ++i) {
            if (x != 0 && num % x == 0) 
                ++cnt;
            x %= mod;
            x = x * 10 + (s.charAt(i) - '0');
        }
        if (x != 0 && num % x == 0) 
            ++cnt;
        return cnt;
    }
}

方法二：子串处理

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public int divisorSubstrings(int num, int k) {
        String s = String.valueOf(num);
        int n = s.length(), cnt = 0;
        for (int i = 0; i + k <= n; ++i) {
            int x = Integer.parseInt(s.substring(i, i + k));
            if (x != 0 && num % x == 0)
                ++cnt;
        }
        return cnt;
    }
}

1984. 学生分数的最小差值

方法一：排序 + 滑动窗口

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int minimumDifference(int[] nums, int k) {
        if (nums.length == 1 || k == 1)
            return 0;
        Arrays.sort(nums);
        int res = 1000001, n = nums.length, l = 0;
        for (int i = 0; i < n; ++i) {
            if (i - l + 1 == k) {
                res = Math.min(res, nums[i] - nums[l]);
                ++l;
            }
        }
        return res;
    }
}

643. 子数组最大平均数 I

方法一：滑动窗口

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public double findMaxAverage(int[] nums, int k) {
        int n = nums.length, l = 0;
        double res = Integer.MIN_VALUE, sum = 0;
        for (int i = 0; i < n; ++i) {
            sum += nums[i];
            if (i - l + 1 == k) {
                res = Math.max(res, sum / k);
                sum -= nums[l++];
            }
        }   
        return res;
    }
}

1343. 大小为 K 且平均值大于等于阈值的子数组数目

方法一：滑动窗口

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int numOfSubarrays(int[] arr, int k, int threshold) {
        int l = 0, cnt = 0, n = arr.length, sum = 0;
        for (int i = 0; i < n; ++i) {
            sum += arr[i];
            if (i - l + 1 == k) {
                if (sum / k >= threshold)
                    ++cnt;
                sum -= arr[l++];
            }
        }
        return cnt;
    }
}

2090. 半径为 k 的子数组平均值

方法一：滑动数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int[] getAverages(int[] nums, int k) {
        int n = nums.length, l = 0;
        int[] avg = new int[n];
        Arrays.fill(avg, -1);
        long sum = 0;
        for (int i = 0; i < n; ++i) {
            sum += nums[i];
            if (i - l + 1 == 2 * k + 1) {
                avg[i - k] = (int) (sum / (2 * k + 1));
                sum -= nums[l++];
            }
        }
        return avg;
    }
}

2379. 得到 K 个黑块的最少涂色次数

方法一：滑动窗口

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int minimumRecolors(String s, int k) {
        int cnt = 0, res = 10000, l = 0, n = s.length();
        for (int i = 0; i < n; ++i) {
            char ch = s.charAt(i);
            if (ch == 'W') 
                ++cnt;
            if (i - l + 1 == k) {
                res = Math.min(res, cnt);
                cnt -= (s.charAt(l++) == 'W' ? 1 : 0);
            }
        }
        return res;
    }
}

1052. 爱生气的书店老板

方法一：滑动窗口

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int maxSatisfied(int[] customers, int[] grumpy, int k) {
        int n = customers.length, l = 0, sum = 0, res = 0;
        for (int i = 0; i < n; ++i)
            sum += grumpy[i] == 0 ? customers[i] : 0;
        for (int i = 0; i < n; ++i) {
            sum += grumpy[i] == 1 ? customers[i] : 0;
            if (i - l + 1 == k) {
                res = Math.max(res, sum);
                if (grumpy[l] == 1)
                    sum -= customers[l];
                ++l;            
            }
        }
        return res;
    }
}

2841. 几乎唯一子数组的最大和

方法一：滑动窗口

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public long maxSum(List<Integer> nums, int m, int k) {
        int n = nums.size(), l = 0;
        long sum = 0, res = 0;
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < n; ++i) {
            int x = nums.get(i);
            sum += x;
            map.put(x, map.getOrDefault(x, 0) + 1);
            if (i - l + 1 == k) {
                if (map.size() >= m)
                    res = Math.max(res, sum);
                int y = nums.get(l++);
                sum -= y;
                map.put(y, map.get(y) - 1);
                if (map.get(y) == 0) 
                    map.remove(y);
            }
        }
        return res;
    }
}

2461. 长度为 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
25
26
class Solution {
    public long maximumSubarraySum(int[] nums, int k) {
        int n = nums.length, cnt = 0, l = 0;
        long res = 0, s = 0;
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < n; ++i) {
            int x = nums[i];
            s += x;
            if (!map.containsKey(x))
                ++cnt;
            map.put(x, map.getOrDefault(x, 0) + 1);
            if (i - l + 1 == k) {
                if (cnt == k)
                    res = Math.max(res, s);
                int y = nums[l++];
                s -= y;
                map.put(y, map.get(y) - 1);
                if (map.get(y) == 0) {
                    map.remove(y);
                    --cnt;
                }
            }
        }
        return res;
    }
}

1423. 可获得的最大点数

方法一：逆向思维 + 滑动窗口

正难则反：从数组中长出长度为n - k，和最小的子数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int maxScore(int[] nums, int k) {
        int sum = 0, s = 0, l = 0, n = nums.length, res = Integer.MAX_VALUE; // n = 7 , k = 3 求长度位4的最小组数组
        for (int i = 0; i < n; ++i) {
            sum += nums[i];
            s += nums[i];
            if (i - l + 1 == n - k) {
                res = Math.min(res, s);
                s -= nums[l++];
            }
        }
        return sum - (n - k == 0 ? 0 : res);
    }
}

2134. 最少交换次数来组合所有的 1 II

方法一：逆向思维

统计1的个数k，以k为窗口，计算窗口内0的数量

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int minSwaps(int[] nums) {
        int l = 0, k = 0, cnt = 0, n = nums.length, res = n;
        for (int x : nums)
            k += x == 1 ? 1 : 0;
        for (int i = 0; i < k; ++i) 
            cnt += nums[i];
        int r = k;
        while (l < n) {
            res = Math.min(res, k - cnt);
            cnt -= nums[l++ % n];
            cnt += nums[r++ % n];   
        }
        return res;
    }   
}
Algorithms > Sliding Window
#滑动窗口
Sliding Window
https://leopol1d.github.io/2023/06/10/sliding-window/
作者
Leopold
发布于
2023年6月10日
许可协议