209. Minimum Size Subarray Sum

, ,

Prefix Sum

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 int minSubArrayLen(int target, int[] nums) {
        int minLength = Integer.MAX_VALUE;

        int[] prefixSumArray = new int[nums.length + 1]; // 前 i 个元素的前缀和
        for (int i = 1; i < prefixSumArray.length; i++) {
            prefixSumArray[i] = prefixSumArray[i - 1] + nums[i - 1];
        }

        for (int i = 0; i < prefixSumArray.length; i++) {
            int targetPrefixSum = prefixSumArray[i] + target;

            int left = i + 1, right = prefixSumArray.length - 1;
            while (left <= right) {
                int mid = (left + right) >>> 1;
                if (prefixSumArray[mid] < targetPrefixSum) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }

            // now: right, left
            if (left < prefixSumArray.length) {
                minLength = Math.min(minLength, left - i);
            }
        }

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

需要注意的是，使用前缀和数组的潜在条件为数组中的元素不能为负数，若含有负数则不能保证前缀和的单调递增特性，此时不能使用二分搜索。同时注意需要有包含 0 个元素的前缀和，否则 [1, 2, 3, 4, 5] 这样的数组在寻找 target = 15 时就无法找到子数组。

Sliding Window

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int minLength = Integer.MAX_VALUE;
        int windowSum = 0;

        int i = 0; // window: [i, j]
        for (int j = 0; j < nums.length; j++) {
            windowSum += nums[j];
            while (windowSum >= target) {
                minLength = Math.min(minLength, j - i + 1);
                windowSum -= nums[i];
                i++;
            }
        }

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

References

209. Minimum Size Subarray Sum
剑指 Offer II 008. 和大于等于 target 的最短子数组