LeetCode 209. Minimum Size Subarray Sum

[Woodyiiiiiii]

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.

**Example: **

Input: s = 7, nums = [2,3,1,2,4,3]
Output: 2
Explanation: the subarray [4,3] has the minimal length under the problem constraint.

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

---

典型的使用“滑动窗口”法。用一个左指针和右指针作为界限，两者之间的区域称为滑动窗口，一般用于连续线性区间且某组子区间所有值满足条件的题型。跟双指针(对撞指针，快慢指针)不同的是，双指针解决的是其所指的两个值满足条件的问题，而不是两个以上的区间问题。
定义一个滑动窗口，如果窗口内的和小于s，右指针加一；否则比较最小长度，左指针加一。

class Solution {
    public int minSubArrayLen(int s, int[] nums) {
        int n = nums.length;
        if (n == 0) return 0;
        int left = 0, right = 0;
        int sum = nums[0], minLen = n + 1;
        while (left < n && right < n) {
            if (sum < s) {
                ++right;
                if (right < n) sum += nums[right];
            }
            else {
                minLen = Math.min(minLen, right - left + 1);
                sum -= nums[left++];
            }
        }
        return minLen == n + 1 ? 0 : minLen;
    }
}

时间复杂度为O(n)。
Follow-up中建议尝试O(nlogn)的方法，显然需要改进二分查找法。看了大佬的讲解，思路如下：声明一个长度为nums.length + 1的sums数组，sums[i]代表数组nums[0]-nums[i - 1]的和，这样sums[j] - sums[i]就是区间[i, j]的子数组和。遍历数组，定位左边界，从右边子数组中查找利用二分查找右边界。二分查找最后会定位到某个值，该值就是大于等于sums[i] + s的临界值。

class Solution {
    private int minLen = Integer.MAX_VALUE;
    public int minSubArrayLen(int s, int[] nums) {
        int n = nums.length;
        if (n == 0) return 0;
        int[] sums = new int[n + 1];
        for (int i = 1; i < n + 1; ++i)
            sums[i] = sums[i - 1] + nums[i - 1];
        for (int i = 0; i < n + 1; ++i) {
            int right = getSubArrRight(sums, s + sums[i], i + 1, n);
            if (right == n + 1) break;
            minLen = Math.min(minLen, right - i);
        }
        return minLen == Integer.MAX_VALUE ? 0 : minLen;
    }
    public int getSubArrRight(int[] sums, int target, int left, int right) {
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (sums[mid] >= target) right = mid - 1;
            else left = mid + 1;
        }
        return left;
    }
}

二分查找可以写函数也可以不写函数。

---

参考资料:

• LeetCode原题
• [LeetCode] 209. Minimum Size Subarray Sum grandyang/leetcode#209

其他滑动窗口问题:

• 3. Longest Substring Without Repeating Characters