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 int minSubArrayLen(int target, int[] nums) {
        int[] prefixSum = new int[nums.length];
        prefixSum[0] = nums[0];
        for (int i = 1; i < nums.length; i++) {
            prefixSum[i] = prefixSum[i - 1] + nums[i];
        }
        int ans = Integer.MAX_VALUE;
        for (int i = 0; i < prefixSum.length; i++) {
            if (prefixSum[i] < target)
                continue;
            int offset = prefixSum[i] - target;
            int leftBound = binarySearch(prefixSum, 0, i - 1, offset);
            ans = Math.min(ans, i - leftBound);
        }
        return ans == Integer.MAX_VALUE ? 0 : ans;
    }

    private int binarySearch(int[] prefixSum, int left, int right, int target) {
        int ans = -1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (prefixSum[mid] <= target) {
                ans = mid;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return ans;
    }
}

prefix sum + binary search

时间复杂度: O(nlogn)
空间复杂度: O(n)

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 left = 0, right = 0, sum = 0, ans = Integer.MAX_VALUE;
        while (right < nums.length) {
            while (right < nums.length && sum < target) {
                sum += nums[right];
                right += 1;
            }
            if (sum < target) {
                break;
            }
            while (left < right && sum >= target) {
                sum -= nums[left];
                left += 1;
            }
            int currLength = right - left + 1;
            ans = Math.min(ans, currLength);
        }
        return ans == Integer.MAX_VALUE ? 0 : ans;
    }
}

sliding window. left表示起点, right表示终点. 我们就开始移动right, 直到某个位置发现sum >= target, 我们停止. 当然right需要在nums的范围内移动. right停止后, 我们看一下当前sum是否大于等于target, 如果没有, 那么目前框起来的区域也累积不到target, 我们直接break. 如果可以, 那就说明在当前left的情况下, 最小的区域就是[left, right), 此时right再移动也没有必要因为在left开头的区域中, 此时是最小的. 此时我们移动left, 看能不能更小. 移动left的时候, sum在不断变小. 新left必须到达right这个位置(不包括right)才能大于等于target, 因为我们在旧left的时候尚且要到达right这个位置, 更何况新left的sum更小, 因此至少要到right. 于是我们移动left, 直到某个时刻, sum小于target了, 我们就知道此时位置的上一个即left - 1处到right构成的区域还是大于target的, 即区域[left - 1, right). 此时我们计算这个区域长度并记录到ans中. 接着我们继续移动right即可.

时间复杂度: O(n)
空间复杂度: O(1)