【算法】滑动窗口题单——3.不定长滑动窗口（求最短/最小）⭐ 删除最短的子数组使剩余数组有序

题单来源：https://leetcode.cn/problems/minimum-size-subarray-in-infinite-array/solutions/2464878/hua-dong-chuang-kou-on-shi-jian-o1-kong-cqawc/

209. 长度最小的子数组

https://leetcode.cn/problems/minimum-size-subarray-sum/description/

提示：

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

进阶：

如果你已经实现 O(n) 时间复杂度的解法, 请尝试设计一个 O(n log(n)) 时间复杂度的解法。

O(n)滑动窗口

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int n = nums.length, ans = n + 1, s = 0;
        for (int l = 0, r = 0; r < n; ++r) {
            s += nums[r];
            while (s - nums[l] >= target) s -= nums[l++];
            if (s >= target) ans = Math.min(ans, r - l + 1);
        }
        return ans == n + 1? 0: ans;
    }
}
1
2
3
4
5
6
7
8
9
10
11

O(nlogn) 前缀和+二分查找

枚举左端点，二分查找右端点。

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int n = nums.length, ans = n + 1;
        int[] s = new int[n + 1];
        for (int i = 1; i <= n; ++i) s[i] = s[i - 1] + nums[i - 1];
        for (int i = 0; i < n; ++i) {
            int l = i, r = n, t = target + s[i];
            while (l < r) {
                int mid = l + r >> 1;
                if (s[mid] >= t) r = mid;
                else l = mid + 1;
            }
            if (s[l] >= t) ans = Math.min(ans, l - i);
        }
        return ans == n + 1? 0: ans;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

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

https://leetcode.cn/problems/replace-the-substring-for-balanced-string/description/

提示：

1 <= s.length <= 10^5
s.length 是 4 的倍数
s 中只含有 'Q', 'W', 'E', 'R' 四种字符

需要满足的条件是窗口外的各个元素的数量都<=n/4，这样就可以完成替换。

class Solution {
    public int balancedString(String s) {
        int n = s.length(), ans = n;
        int[] cnt = new int[128];
        for (char ch: s.toCharArray()) cnt[ch]++;
        for (int l = 0, r = 0; l < n; ++l) {
            while (!check(cnt, n / 4) && r < n) --cnt[s.charAt(r++)];
            if (check(cnt, n / 4)) ans = Math.min(ans, r - l);
            ++cnt[s.charAt(l)];
        }
        return ans;
    }

    public boolean check(int[] cnt, int x) {
        return cnt['Q'] <= x && cnt['W'] <= x && cnt['E'] <= x && cnt['R'] <= x;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

1574. 删除最短的子数组使剩余数组有序⭐

https://leetcode.cn/problems/shortest-subarray-to-be-removed-to-make-array-sorted/description/

提示：

1 <= arr.length <= 10^5
0 <= arr[i] <= 10^9

定义好 l 和 r 的含义，分别是第一个非递减子数组的结束位置和第二个非递减子数组的开始位置，而不是中间被删除的子数组的两端。

枚举左端点，移动右端点

class Solution {
    public int findLengthOfShortestSubarray(int[] arr) {
        int n = arr.length, r = n - 1;      // r表示下一个非递减数组的开始位置
        while (r > 0 && arr[r - 1] <= arr[r]) r--;
        if (r == 0) return 0;
        int ans = r;
        // l表示第一个非递减数组的结束位置
        for (int l = 0; l == 0 || arr[l - 1] <= arr[l]; ++l) {
            while (r < n && arr[r] < arr[l]) ++r;
            ans = Math.min(ans, r - l - 1);
        }
        return ans;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

枚举右端点，移动左端点

class Solution {
    public int findLengthOfShortestSubarray(int[] arr) {
        int n = arr.length, l = 0;      // l表示第一个非递减数组的结束位置
        while (l + 1 < n && arr[l + 1] >= arr[l]) l++;
        if (l == n - 1) return 0;
        int ans = n - l - 1;
        // r表示下一个非递减数组的开始位置
        for (int r = n - 1; r == n - 1 || arr[r] <= arr[r + 1]; --r) {
            while (l >= 0 && arr[l] > arr[r]) l--;
            ans = Math.min(ans, r - l - 1);
        }
        return ans;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

76. 最小覆盖子串

https://leetcode.cn/problems/minimum-window-substring/description/

提示：

m == s.length
n == t.length
1 <= m, n <= 10^5
s 和 t 由英文字母组成

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

维护窗口中的字符出现数量。
枚举右端点，根据条件收缩左端点即可。

class Solution {
    int[] cnt1 = new int[128], cnt2 = new int[128];

    public String minWindow(String s, String t) {
        for (char ch: t.toCharArray()) cnt2[ch]++;
        String ans = "";
        int mnL = s.length() + 1;
        for (int l = 0, r = 0; r < s.length(); ++r) {
            cnt1[s.charAt(r)]++;
            while (l < r && cnt1[s.charAt(l)] > cnt2[s.charAt(l)]) cnt1[s.charAt(l++)]--;
            if (check() && mnL > r - l + 1) {
                mnL = r - l + 1;
                ans = s.substring(l, r + 1);
            }
        }
        return ans;
    }

    public boolean check() {
        for (int i = 0; i < 128; ++i) {
            if (cnt1[i] < cnt2[i]) return false;
        }
        return true;
    }
}
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