1. 长度最小的子数组

题目描述

给定一个含有 n 个正整数的数组和一个正整数 target 。

找出该数组中满足其总和大于等于 target 的长度最小的 子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度**。**如果不存在符合条件的子数组，返回 0 。

示例 1：

1
2
3
输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。

示例 2：

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

示例 3：

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

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int n = nums.length;
        int ans = n + 1;
        int sum = 0; // 子数组元素和
        int left = 0;
        for (int right = 0; right < n; right++) {
            // 一直往右遍历
            sum += nums[right];
            while (sum - nums[left] >= target) { // 如果可以减去左端，来缩小子数组大小
                sum -= nums[left];
                left++;
            }
            if (sum >= target) {
                // 同时更新最小窗口数
                ans = Math.min(ans, right - left + 1);
            }
        }
        return ans <= n ? ans : 0;
    }
}

优化

只要达到target ，就更新最小数组长度，

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int left = 0;
        int right = 0;
        int res = Integer.MAX_VALUE;
        int sum = 0;
        while(right < nums.length) {
            sum += nums[right];
            right++;
            while(sum >= target) {
                res = Math.min(res, right - left);
                sum -= nums[left];
                left++;
            }
        }

        return res == Integer.MAX_VALUE ? 0 : res;
    }
}

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

题目描述

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

示例 1:

1
2
3
输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。注意 "bca" 和 "cab" 也是正确答案。

示例 2:

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

示例 3:

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

提示：

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

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int lengthOfLongestSubstring(String s) {
        char[] S = s.toCharArray();
        int n = S.length;
        int[] cnt = new int[128];
        int ans = 0;
        int left = 0;
        for (int right = 0; right < n; right++) {
            char c = S[right];
            cnt[c]++;
            while (cnt[c] > 1) {
                cnt[S[left]]--;
                left++;
            }
            ans = Math.max(ans, right - left + 1);
        }
        return ans;
    }
}

思路

1
用每个出现过的字符作为集合的索引，索引>1时，移除左边元素直到索引减为1，记录最长长度

713. 乘积小于 K 的子数组

题目描述

给定一个整数数组 nums 和一个整数 k。

请你返回 子数组 内所有元素的 乘积严格小于 k 的连续子数组的数目。

示例 1：

1
2
3
4
输入：nums = [10,5,2,6], k = 100
输出：8
解释：8 个乘积小于 100 的子数组分别为：[10]、[5]、[2]、[6]、[10,5]、[5,2]、[2,6]、[5,2,6]。
需要注意的是 [10,5,2] 并不是乘积小于 100 的子数组。

示例 2：

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

提示:

  • 1 <= nums.length <= 3 * 104
  • 1 <= nums[i] <= 1000
  • 0 <= k <= 106

题解

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 numSubarrayProductLessThanK(int[] nums, int k) {
        // 
        if (k <= 1) {
            return 0;
        }

        int n = nums.length;
        int left = 0;
        int ji = 1;
        int ans = 0;
        for (int right = 0; right < n; right++) {
            ji = ji * nums[right];
            while (ji >= k) {
                ji = ji / nums[left];
                left++;
            }
            // ans++;
            // 子数组
            ans += right - left + 1;
        }
        return ans;
    }
}

思路

这样遍历可以得到满足要求的以 left 开头的大数组，每个大数组可以拆分成 right - left + 1 个小数组

right - left + 1 为大数组长度，长度为4的大数组可以被分为4个以left开头的小数组，不会重复

image-20261004104115914

3090. 每个字符最多出现两次的最长子字符串

题目描述

给你一个字符串 s ，请找出满足每个字符最多出现两次的最长子字符串，并返回该子字符串的 最大 长度。

示例 1：

输入： s = “bcbbbcba”

输出： 4

解释：

以下子字符串长度为 4，并且每个字符最多出现两次："bcbbbcba"。

示例 2：

输入： s = “aaaa”

输出： 2

解释：

以下子字符串长度为 2，并且每个字符最多出现两次："aaaa"。

提示：

  • 2 <= s.length <= 100
  • s 仅由小写英文字母组成。

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int maximumLengthSubstring(String s) {
        char[] S = s.toCharArray();
        int n = S.length;
        int[] cnt = new int[128];
        int ans = 0;
        int left = 0;
        for (int right = 0; right < n; right++) {
            char c = S[right];
            cnt[c]++;
            while (cnt[c] > 2) {
                cnt[S[left]]--;
                left++;
            }
            ans = Math.max(ans, right - left + 1);
        }
        return ans;
    }
}

思路

同3

2958. 最多 K 个重复元素的最长子数组

题目描述

给你一个整数数组 nums 和一个整数 k 。

一个元素 x 在数组中的 频率 指的是它在数组中的出现次数。

如果一个数组中所有元素的频率都 小于等于 k ，那么我们称这个数组是 好 数组。

请你返回 nums 中 最长好 子数组的长度。

子数组 指的是一个数组中一段连续非空的元素序列。

示例 1：

1
2
3
4
输入：nums = [1,2,3,1,2,3,1,2], k = 2
输出：6
解释：最长好子数组是 [1,2,3,1,2,3] ，值 1 ，2 和 3 在子数组中的频率都没有超过 k = 2 。[2,3,1,2,3,1] 和 [3,1,2,3,1,2] 也是好子数组。
最长好子数组的长度为 6 。

示例 2：

1
2
3
4
输入：nums = [1,2,1,2,1,2,1,2], k = 1
输出：2
解释：最长好子数组是 [1,2] ，值 1 和 2 在子数组中的频率都没有超过 k = 1 。[2,1] 也是好子数组。
最长好子数组的长度为 2 。

示例 3：

1
2
3
4
输入：nums = [5,5,5,5,5,5,5], k = 4
输出：4
解释：最长好子数组是 [5,5,5,5] ，值 5 在子数组中的频率没有超过 k = 4 。
最长好子数组的长度为 4 。

提示：

  • 1 <= nums.length <= 105
  • 1 <= nums[i] <= 109
  • 1 <= k <= nums.length

错误

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int maxSubarrayLength(int[] nums, int k) {
        if (k < 1) {
            return 0;
        }
        long[] cnt = new long[1000000000];
        int left = 0;
        int n = nums.length;
        int ans = 0;
        for (int right = 0; right < n; right++) {
            cnt[nums[right]]++;
            while(cnt[nums[right]] > k) {
                cnt[nums[left]]--;
                left++;
            }
            ans = Math.max(ans, right - left + 1);
        }
        return ans;
    }
}
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
class Solution {
    public int maxSubarrayLength(int[] nums, int k) {
        if (k < 1) {
            return 0;
        }
        HashMap<Integer, Integer> cnt = new HashMap<>();
        int left = 0;
        int n = nums.length;
        int ans = 0;
        for (int right = 0; right < n; right++) {
            int rVal = nums[right];
            cnt.put(rVal, cnt.getOrDefault(rVal, 0) + 1);

            // 只要窗口内 右端点元素频次超过k，就不断左移left
            // 本题特性：新加入的nums[right]才有可能造成超标！
            while (cnt.get(rVal) > k) {
                int lVal = nums[left];
                cnt.put(lVal, cnt.get(lVal) - 1);
                left++;
            }
            ans = Math.max(ans, right - left + 1);
        }
        return ans;
    }
}

优化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int maxSubarrayLength(int[] nums, int k) {
        int ans = 0;
        int left = 0;
        Map<Integer, Integer> cnt = new HashMap<>();
        for (int right = 0; right < nums.length; right++) {
            cnt.merge(nums[right], 1, Integer::sum);
            while (cnt.get(nums[right]) > k) {
                cnt.merge(nums[left], -1, Integer::sum);
                left++;
            }
            ans = Math.max(ans, right - left + 1);
        }
        return ans;
    }
}

merge() 方法：key 不存在存默认值；key 存在，执行合并函数算出新值写入；合并函数返回 null，则移除 key。

2730. 找到最长的半重复子字符串

题目描述

给你一个下标从 0 开始的字符串 s ，这个字符串只包含 0 到 9 的数字字符。

如果一个字符串 t 中至多有一对相邻字符是相等的，那么称这个字符串 t 是 半重复的 。例如，"0010" 、"002020" 、"0123" 、"2002" 和 "54944" 是半重复字符串，而 "00101022" （相邻的相同数字对是 00 和 22）和 "1101234883" （相邻的相同数字对是 11 和 88）不是半重复字符串。

请你返回 s 中最长 半重复 子字符串 的长度。

示例 1：

**输入：**s = “52233”

**输出：**4

解释：

最长的半重复子字符串是 “5223”。整个字符串 “52233” 有两个相邻的相同数字对 22 和 33，但最多只能选取一个。

示例 2：

**输入：**s = “5494”

**输出：**4

解释：

s 是一个半重复字符串。

示例 3：

**输入：**s = “1111111”

**输出：**2

解释：

最长的半重复子字符串是 “11”。子字符串 “111” 有两个相邻的相同数字对，但最多允许选取一个。

提示：

  • 1 <= s.length <= 50
  • '0' <= s[i] <= '9'

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int longestSemiRepetitiveSubstring(String s) {
        char[] c = s.toCharArray();
        int left = 0;
        int ans = 1;
        int cnt = 0;
        for (int right = 1; right < c.length; right++) {
            if (c[right] == c[right - 1]) {
                cnt++;
            }
            while (cnt > 1) {
                if (c[left] == c[left + 1]) {
                    cnt--;
                }
                left++;
            }
            ans = Math.max(ans, right - left + 1);
        }
        return ans;
    }
}

1004. 最大连续1的个数 III

题目描述

给定一个二进制数组 nums 和一个整数 k，假设最多可以翻转 k 个 0 ，则返回执行操作后 数组中连续 1 的最大个数 。

示例 1：

1
2
3
4
输入：nums = [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
输入：nums = [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 <= nums.length <= 105
  • nums[i] 不是 0 就是 1
  • 0 <= k <= nums.length

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int longestOnes(int[] nums, int k) {
        int ans = 0;
        int l = 0;
        int n = nums.length;
        int cnt = 0;
        for (int r = 0; r < n; r++) {
            if (nums[r] == 0) {
                cnt++;
            }
            while (cnt > k) {
                if (nums[l] == 0) {
                    cnt--;
                }
                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
22
23
class Solution {
    public int longestOnes(int[] nums, int k) {
        int ans = 0;
        int l = 0;
        int n = nums.length;
        for(int r = 0; r < n; r++){
            if(nums[r] == 0){
                if(k <= 0) {
                    ans = Math.max(ans, r - l);
                    while(k <= 0){
                        if(nums[l] == 0){
                            k++;
                        }
                        l++;
                    }
                }
                k--;
            }
        }
        ans = Math.max(ans, n - l);
        return ans;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int longestOnes(int[] nums, int k) {
        int ans = 0;
        int cnt0 = 0;
        int left = 0;
        for (int right = 0; right < nums.length; right++) {
            cnt0 += 1 - nums[right]; // 0 变成 1，用来统计 cnt0
            while (cnt0 > k) {
                cnt0 -= 1 - nums[left];
                left++;
            }
            ans = Math.max(ans, right - left + 1);
        }
        return ans;
    }
}

亮点

在遇见统计出现次数为二进制数时，可以用 1 - num 来统计0出现的次数

2962. 统计最大元素出现至少 K 次的子数组

题目描述

给你一个整数数组 nums 和一个 正整数 k 。

请你统计有多少满足 「 nums 中的 最大 元素」至少出现 k 次的子数组，并返回满足这一条件的子数组的数目。

子数组是数组中的一个连续元素序列。

示例 1：

1
2
3
输入：nums = [1,3,2,3,3], k = 2
输出：6
解释：包含元素 3 至少 2 次的子数组为：[1,3,2,3]、[1,3,2,3,3]、[3,2,3]、[3,2,3,3]、[2,3,3] 和 [3,3] 。

示例 2：

1
2
3
输入：nums = [1,4,2,1], k = 3
输出：0
解释：没有子数组包含元素 4 至少 3 次。

提示：

  • 1 <= nums.length <= 105
  • 1 <= nums[i] <= 106
  • 1 <= k <= 105

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public long countSubarrays(int[] nums, int k) {
        int mx = Arrays.stream(nums).max().getAsInt();
        long ans = 0;
        int cnt = 0;
        int left = 0;
        for (int right = 0; right < nums.length; right++){
            if (nums[right] == mx) {
                cnt++;
            }
            while (cnt == k) {
                if (nums[left] == mx) {
                    cnt--;
                }
                left++;
            }
            ans += left;
        }
        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
class Solution {
    public long countSubarrays(int[] nums, int k) {
        int mx = 0;
        for (int x : nums) {
            mx = Math.max(mx, x);
        }

        long ans = 0;
        int cntMx = 0, left = 0;
        for (int x : nums) {
            if (x == mx) {
                cntMx++;
            }
            while (cntMx == k) {
                if (nums[left] == mx) {
                    cntMx--;
                }
                left++;
            }
            ans += left;
        }
        return ans;
    }
}

思路

只需要保持 区间内 只有 k 个最大元素，此时左指针即为当前区间负责的所有子区间数(0~left)

即只要该区间有k个最大元素，则该区间前0到left的所有区间 + left~right 的区间最大元素数必 > k

image-20261004202106036

总结

获取数组中最大值的方法：

1
2
3
4
5
6
int mx = Arrays.stream(nums).max().getAsInt();

int mx = 0;
for (int x : nums) {
    mx = Math.max(mx, x);
}

2302. 统计得分小于 K 的子数组数目

题目描述

一个数组的 分数 定义为数组之和 乘以 数组的长度。

  • 比方说，[1, 2, 3, 4, 5] 的分数为 (1 + 2 + 3 + 4 + 5) * 5 = 75 。

给你一个正整数数组 nums 和一个整数 k ，请你返回 nums 中分数 严格小于 k 的 非空整数子数组数目。

子数组 是数组中的一个连续元素序列。

示例 1：

1
2
3
4
5
6
7
8
9
10
11
输入：nums = [2,1,4,3,5], k = 10
输出：6
解释：
有 6 个子数组的分数小于 10 ：
- [2] 分数为 2 * 1 = 2 。
- [1] 分数为 1 * 1 = 1 。
- [4] 分数为 4 * 1 = 4 。
- [3] 分数为 3 * 1 = 3 。 
- [5] 分数为 5 * 1 = 5 。
- [2,1] 分数为 (2 + 1) * 2 = 6 。
注意，子数组 [1,4] 和 [4,3,5] 不符合要求，因为它们的分数分别为 10 和 36，但我们要求子数组的分数严格小于 10 。

示例 2：

1
2
3
4
5
6
输入：nums = [1,1,1], k = 5
输出：5
解释：
除了 [1,1,1] 以外每个子数组分数都小于 5 。
[1,1,1] 分数为 (1 + 1 + 1) * 3 = 9 ，大于 5 。
所以总共有 5 个子数组得分小于 5 。

提示：

  • 1 <= nums.length <= 105
  • 1 <= nums[i] <= 105
  • 1 <= k <= 1015

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public long countSubarrays(int[] nums, long k) {
        int left = 0;
        long ans = 0;
        long sum = 0;
        for (int right = 0; right < nums.length; right++) {
            sum += nums[right];
            while (sum * (right - left + 1) >= k) {
                sum -= nums[left];
                left++;
            }
            ans += right - left + 1;
        }
        return ans;
    }
}

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

题目描述

给你一个整数数组 nums 和一个整数 x 。每一次操作时，你应当移除数组 nums 最左边或最右边的元素，然后从 x 中减去该元素的值。请注意，需要 修改 数组以供接下来的操作使用。

如果可以将 x 恰好 减到 0 ，返回 最小操作数 ；否则，返回 -1 。

示例 1：

1
2
3
输入：nums = [1,1,4,2,3], x = 5
输出：2
解释：最佳解决方案是移除后两个元素，将 x 减到 0 。

示例 2：

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

示例 3：

1
2
3
输入：nums = [3,2,20,1,1,3], x = 10
输出：5
解释：最佳解决方案是移除后三个元素和前两个元素（总共 5 次操作），将 x 减到 0 。

提示：

  • 1 <= nums.length <= 105
  • 1 <= nums[i] <= 104
  • 1 <= x <= 109

题解

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
class Solution {
    public int minOperations(int[] nums, int x) {
        int target = -x;
        for (int num : nums) {
            target += num;
        }
        if (target < 0) {
            return -1; // 全部移除也无法满足要求
        }

        int n = nums.length;
        int ans = -1;
        int sum = 0;
        int left = 0;
        for (int right = 0; right < n; right++) {
            sum += nums[right];
            while (sum > target) {
                sum -= nums[left];
                left++; // 缩小子数组长度
            }
            if (sum == target) {
                ans = Math.max(ans, right - left + 1);
            }
        }
        return ans < 0 ? -1 : n - ans;
    }
}

思路

逆向思维，只需先找到和为 总和 - x 的最小长度 ans 数组，再用总长度减去 ans 即为所求次数