Minimum Size Subarray Sum

Question

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.

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

Solution

這題算是有解出來，我最初的解法是用 Queue 去記錄走過的點，然後如果超過 s，就開始試著把前面的點 poll()。對照解答，其實是運用到了 two pointers 的概念

    int n = nums.size();
    int ans = INT_MAX;
    int left = 0;
    int sum = 0;
    for (int i = 0; i < n; i++) {
        sum += nums[i];
        while (sum >= s) {
            ans = min(ans, i + 1 - left);
            sum -= nums[left++];
        }
    }
    return (ans != INT_MAX) ? ans : 0;

另外一種解法得到的是 O(nlogn)。當然，看到 logn 就要想到要馬二分，要馬用 logn 的數據結構。這邊都給你 array 了，當然是要用二分法。這裡有個滿重要的概念是，要用 binarySearch 的先決條件在：array 必須是 sorted，但這邊我們並不能 sort 這個 array。不過，由於題目告訴我們，array 裡全部都是 positive integer，這代表，該 array 的 iteration sum 會是遞增的，也就是 sorted。加上如果要求某一區間的和，記得要想到可以用 sum[j] - sum[i]，這樣就代表從 i+1 ~ j 這段區間的總和

其實這題要用二分法不是那麼直觀跟容易。要特別注意的是，這邊的二分法用九章教的會有 IndexOutOfBounds exception。不過這邊我其實沒有想得很清楚，待之後想清楚了再補上

    public int minSubArrayLen(int s, int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }

        int[] sums = new int[nums.length + 1];
        for (int i = 1; i < sums.length; i++) {
            sums[i] = sums[i - 1] + nums[i - 1];
        }

        int len = Integer.MAX_VALUE;
        for (int i = 0; i < sums.length; i++) {
            int end = binarySearch(i + 1, sums.length - 1, sums[i] + s, sums);
            if (end == sums.length) {
                break;
            }
            if (end - i < len) {
                len  = end - i;
            }
        }

        return len == Integer.MAX_VALUE? 0 : len;
    }

    public int binarySearch(int start , int end, int target, int[] sums) {
        while (start <= end) {
            int mid = start + (end - start) / 2;
            if (sums[mid] >= target) {
                end = mid - 1;
            } else {
                start = mid + 1;
            }
        }

        return start;
    }

事後想出來為什麼九章的算法會錯誤。第一個需要調整的地方是 binarySearch 傳入的參數，原本是 i + 1，但因為九章的 binarySearch 會 check sums[start] 跟 sums[end]，因此要改回 i。再來是 binarySearch 裡面，最後除了 return start 跟 return end 的情況外，還要再多一個 return 當沒有找到的情況。我就是漏了這個，所以答案才會錯

    public int minSubArrayLen(int s, int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }

        int[] sums = new int[nums.length + 1];
        for (int i = 1; i < sums.length; i++) {
            sums[i] = sums[i - 1] + nums[i - 1];
        }

        int len = Integer.MAX_VALUE;
        for (int i = 0; i < sums.length; i++) {
            int end = binarySearch(i, sums.length - 1, sums[i] + s, sums);
            if (end == -1) {
                continue;
            }
            if (end - i < len) {
                len  = end - i;
            }
        }

        return len == Integer.MAX_VALUE? 0 : len;
    }

    public int binarySearch(int start , int end, int target, int[] sums) {
        while (start + 1 < end) {
            int mid = start + (end - start) / 2;
            if (sums[mid] >= target) {
                end = mid;
            } else {
                start = mid;
            }
        }

        if (sums[start] >= target) {
            return start;
        } else if (sums[end] >= target) {
            return end;
        }
        return -1;
    }

九章強化班有提出另外一種解法，就是一開始先去 for i 跟 for j，假如走到 (0,3) 發現是第一次 >= s，更新完 ans 之後，直接把 i + 1。這邊的思路是在於，如果 (0,3) 是第一次 >= s，那麼代表 (1,0), (1,1), (1,2) 都不可能 >=s

    int j = 0, i = 0;
    int sum = 0;
    int ans = Integer.MAX_VALUE;
    for (int i =0; i < nums.length; i++) {
        while (j < nums.length && sum < s) {
            sum += nums[j];
            j++;
        }
        if (sum >= s) {
            ans = Math.min(ans, j - i);
        }

        sum -= nums[i];
    }

    return ans == Integer.MAX_VALUE? -1 : ans;