Minimum Subarray for Sum

给定一个由 n 个整数组成的数组和一个正整数 s ,请找出该数组中满足其和 ≥ s 的最小长度子数组。如果无解,则返回 -1。

样例

给定数组 [2,3,1,2,4,3] 和 s = 7, 子数组 [4,3] 是该条件下的最小长度子数组。

挑战

如果你已经完成了O(n)时间复杂度的编程,请再试试 O(n log n)时间复杂度。

Solution

我们需要定义两个指针left和right,分别记录子数组的左右的边界位置,然后我们让right向右移,直到子数组和大于等于给定值或者right达到数组末尾,此时我们更新最短距离,并且将left像右移一位,然后再sum中减去移去的值,然后重复上面的步骤,直到right到达末尾,且left到达临界位置,即要么到达边界,要么再往右移动,和就会小于给定值。

two pointers.当当前sum已经满足条件后,将start往后移至不满足条件的index为止,再更新结果。

Complexity

复杂度O(n)。

Code

public class Solution {
    /**
     * @param nums: an array of integers
     * @param s: an integer
     * @return: an integer representing the minimum size of subarray
     */
    public int minimumSize(int[] nums, int s) {
        if (nums == null || nums.length == 0) {
            return -1;
        }
        int res = -1;
        int sum = 0;
        int start = 0;
        for (int end = 0; end < nums.length; end++) {
            sum += nums[end];
            if (sum >= s) {
                if (start == end) {
                    res = 1;
                    break;
                }
                while (start < end && sum - nums[start] >= s) {
                    sum -= nums[start];
                    start++;
                }
                res = res == -1 ? end - start + 1 : Math.min(res, end - start + 1);
            }
        }
        return res == -1 ? -1 : res;
    }
}