209. Minimum Size Subarray Sum

Leetcode Array Two Pointers Binary Search

Given an array of $n$ positive integers and a positive integer $s$, find the minimal length of a contiguous subarray of which the sum $\ge 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$时，试图缩小窗口，知道子数组的和小于$s$。重复此过程，找到长度最小的滑动窗口。类似的题目可参照LeetCode 76. Minimum Window Substring。算法时间复杂度为$O(n)$。

public int minSubArrayLen(int s, int[] nums) {      
    // 左右指针
    int l = 0, r = 0;

    // 数组的长度
    int n = nums.length;

    // 和大于等于s的最小子数组长度
    int minLength = n + 1;

    // 子数组的和
    int sum = 0;

    while (r < n) {
        // 子数组的和加上当前数字
        sum += nums[r];

        // 子数组的和大于等于s
        while (sum >= s) {
            // 如果该子数组的长度为最小, 更新最小长度
            if (r - l + 1 < minLength)
                minLength = r - l + 1;

            // 移动左指针, 并更新子数组的和
            sum -= nums[l++];
        }
        r++;
    }
    return minLength > n ? 0 : minLength;    
}

题目还说了试着另一种时间复杂度为$O(n \log n)$的算法。一看到$O(n \log n)$的算法，可以想到二分查找。但是数组并不能排序，因为数字的顺序是题目的关键。那么怎么得到有序的数组呢？由于题目限制了所有的数字必须是正整数，所以累加和是有序的！一种巧妙的办法是将原数组nums[i]转换为前$i$个数字的和的数组sums[i]。因此一个子数组的和可以表示为两个累加和的差。这样给定子数组的起点，子数组的终点可以通过二分查找找到。

public int minSubArrayLen(int s, int[] nums) {
    int n = nums.length;
    int[] sums = new int[n + 1];
    // sums[i]为nums中前i个数字的和
    for (int i = 0; i < n; i++)
        sums[i + 1] = sums[i] + nums[i];

    // 和大于等于s的最小子数组长度
    int minLength = n + 1;

    for (int start = 0; start < n; start++) {
        // 以start为开始位置，在接下来的数组中，寻找和为sums[start] + s的值的位置
        int end = binarySearch(start + 1, n, sums[start] + s, sums);

        // 找不到，即使找遍所有的和。
        // 由于现在找不到，接下来start变大，寻找区间变小，更找不到了，所以停止搜索
        if (end > n) break; 

        // 如果该子数组的长度为最小, 更新最小长度
        if (minLength >  end - start) minLength = end - start;
    }
    return minLength > n ? 0 : minLength;
}


// 二分查找
private int binarySearch(int lo, int hi, int key, int[] keys) {
    if (lo > hi) return lo;
    int mid = (lo + hi) / 2;
    int cmp = keys[mid] - key;
    if (cmp < 0) return binarySearch(mid + 1, hi, key, keys);
    else if (cmp > 0) return binarySearch(lo, mid - 1, key, keys);
    else return mid;
}