209. Minimum Size Subarray Sum

发表于 | 分类于

Given an array of n positive integers and a positive integer s, find the minimal length of a contiguous subarray of which the sum ≥ s. If there isn’t one, return 0 instead.

For example, given the array [2,3,1,2,4,3] and s = 7,
the subarray [4,3] has the minimal length under the problem constraint.

More practice:

If you have figured out the O(n) solution, try coding another solution of which the time complexity is O(n log n).

解法1：dynamic window O(N)

动态窗口的一种应用。用左右两个指针维护一个窗口，先移动右指针直到加和>=sum, 然后在开始移动左指针，每次移动判断加和是否还满足并且更新最小的差距。
C++

1

Java

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
public class Solution {
    public int minSubArrayLen(int s, int[] nums) {
        if (nums.length == 0) {
            return 0;
        }
        int left = 0, right = 0, n = nums.length, sum = 0;
        // left, right is a dynamic window
        int res = Integer.MAX_VALUE;
        while (right < n) {
            while (sum < s && right < n) {
                sum += nums[right++];
            }
            while (sum >= s) {
                res = Math.min(res, right - left);
                sum -= nums[left++];
            }
        }
        return res == Integer.MAX_VALUE ? 0 : res;
    }
}

用binary search的条件是数组一定是一定程度上有序的。这里把数组变成了一个累加的数组。然后对于每一个加和
sum， 寻找在之后的第一个数字k使得k>=sum+s，找到之后更新坐标。
Java

lang: java
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
33
34
35
36
37
38
39
40
41
42
43
44
45
public class Solution {
    public int minSubArrayLen(int s, int[] nums) {
        if (nums.length == 0) {
            return 0;
        }
        // Create a helper array
        int n = nums.length;
        int[] helper = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            helper[i] = helper[i - 1] + nums[i - 1];
        }
        int res = Integer.MAX_VALUE;
        for (int i =  0; i < n; i++) {
            int temp = binarySearch(helper, i + 1, n, s + helper[i]);
            if (temp != -1) {
                res = Math.min(res, temp - i);
            }
        }
        return res == Integer.MAX_VALUE ? 0 : res;
    }
    private int binarySearch(int[] nums, int left, int right, int target) {
        // Find the first element in nums that is larger or equal to the target
        while (left + 1 < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < target) {
                left = mid;
            } else if (nums[mid] >= target) {
                right = mid;
            }
        }
        if (nums[left] >= target) {
            return left;
        } else if (nums[right] >= target) {
            return right;
        } else {
            return -1;
        }
    }
}