1. 例题
560. 和为 K 的子数组
862. 和至少为 K 的最短子数组
3097. 或值至少为 K 的最短子数组 II
2. 思路
三者都用到了动态规划的思想，但需要结合不同的数据结构进行处理。
2.1 LC560 和为 K 的子数组个数
做法：前缀和 + 哈希表
我们需要统计数组中和为 k 的子数组个数，可以先求前缀和数组 prefix（包含自身），然后推导一下递推式。
要找 [j, … ,i] 的和为k，其实就是找 prefix[i] - prefix[j - 1] = k
就是要找有多少个 prefix[j - 1] = prefix[i] - k
因此用一个哈希表来记录所有 prefix 的个数即可，对应代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| class Solution {
public int subarraySum(int[] nums, int k) {
int n = nums.length;
HashMap<Integer, Integer> map = new HashMap<>();
map.put(0, 1);
int res = 0;
int sum = 0;
for (int i = 0; i < n; i++) {
sum += nums[i];
if (map.containsKey(sum - k)) {
res += map.get(sum - k);
}
map.put(sum, map.getOrDefault(sum, 0) + 1);
}
return res;
}
}
|
2.2 LC862 和至少为 k 的最短子数组长度
在 LC560 上进行改编，变成了：和至少为 k、求最短子数组长度
不变的是要求前缀和，但要求最短子数组，可以使用一个单调的双端队列进行记录
当前（下标）前缀和 减去 队列第一个元素（下标）对应的前缀和 >= k 时，就更新一下长度，然后将这个元素出队。这个过程要保证队列中下标对应的前缀和是从小到大的。
Tips：求数组中 第一个符合xxx条件 的元素的位置，就要联想到单调栈、单调队列
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
| class Solution {
public int shortestSubarray(int[] nums, int k) {
int n = nums.length;
long[] preSum = new long[n + 1];
for (int i = 0; i < n; i++) {
preSum[i + 1] = preSum[i] + nums[i];
}
Deque<Integer> dq = new ArrayDeque<Integer>();
int minLength = Integer.MAX_VALUE;
for (int i = 0; i <= n; i++) {
long curSum = preSum[i];
while (!dq.isEmpty() && curSum - preSum[dq.peekFirst()] >= k) {
minLength = Math.min(minLength, i - dq.pollFirst());
}
while (!dq.isEmpty() && curSum <= preSum[dq.peekLast()]) {
dq.pollLast();
}
dq.offerLast(i);
}
minLength = minLength == Integer.MAX_VALUE ? -1 : minLength;
return minLength;
}
}
|
2.3 LC3097 或值至少为 k 的最短子数组长度
LC560 和 LC862 都可以用前缀和 + 数据结构解决问题，该题没办法再用前缀xxx，因为前缀和相减可以得到某一段子数组的区间和，但或运算不行，也没有 “前缀或” 这种概念。
因此需要另外一种记录方式，用一个数组记录每个位置到当前位置的 OR 值，并标记可以取的左端点的最大值。
如果 OR 值重复，则需要去重，留下左端点较大的那个。
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
| class Solution {
public int minimumSubarrayLength(int[] nums, int k) {
int minLength = Integer.MAX_VALUE;
List<int[]> ors = new ArrayList<>();
for (int i = 0; i < nums.length; i++) {
ors.add(new int[] { 0, i });
int j = 0;
for (int[] or : ors) {
or[0] |= nums[i];
if (or[0] >= k) {
minLength = Math.min(minLength, i - or[1] + 1);
}
if (ors.get(j)[0] == or[0]) {
ors.get(j)[1] = or[1];
} else {
ors.set(++j, or);
}
}
ors.subList(j + 1, ors.size()).clear();
}
return minLength == Integer.MAX_VALUE ? -1 : minLength;
}
}
|
方法二：利用 OR 的性质，看成集合，a or b 实际上就是 a 与 b 的并集。双层循环操作的时候，nums[i] 逐步往左边并，并存入 nums[j]。
当 i = 1，nums[0] 存的是 nums[0] 并 nums[1]
当 i = 2，nums[0] 存的是 nums[0] 并 nums[1] 并 nums[2]
设想一下，当 nums[2] 是 nums[1] 的子集的时候，继续往左边并就没有意义了，因为并子集进去不会改变结果，因此可以跳出循环。
时间复杂度：O(nlogU)，U=max(nums)
提示：当 a | b = a 时，说明 b 是 a 的子集
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution {
public int minimumSubarrayLength(int[] nums, int k) {
int minLength = Integer.MAX_VALUE;
int n = nums.length;
for (int i = 0; i < n; i++) {
int x = nums[i];
if (x >= k) {
return 1;
}
for (int j = i - 1; j >= 0 && (nums[j] | x) != nums[j]; j--) {
nums[j] |= x;
if (nums[j] >= k) {
minLength = Math.min(minLength, i - j + 1);
}
}
}
return minLength == Integer.MAX_VALUE ? -1 : minLength;
}
}
|
还有更多子数组的相关题目，后续遇到时继续总结。
wechat
alipay
