Minimum Size Subarray Sum

https://leetcode.com/problems/minimum-size-subarray-sum/

解法1

 public int minSubArrayLen(int s, int[] nums) {
        int i = 0;
        if (nums.length == 0) {
            return 0;
        }
        if (nums[i] >= s) {
            return 1;
        }
        int j = i;
        int sum = nums[0];
        int maxLength = 0;

        while (i <= j) {
            if (sum >= s) {
                if (maxLength == 0) {
                    maxLength = j - i + 1;
                }
                maxLength = maxLength <= j - i + 1 ? maxLength : j - i + 1;
                sum = sum - nums[i];
                i++;
                continue;
            }
            if (j < nums.length - 1) {
                j++;
                sum += nums[j];
            } else {
                sum = sum - nums[i];
                i++;
            }
        }
        return maxLength;
    }

解法2

O（NlogN）
参考：https://www.cnblogs.com/grandyang/p/4501934.html

public int minSubArrayLen3(int s, int[] nums) {
        int len = nums.length;
        int[] sums = new int[len + 1];
        int res = len + 1;
        for (int i = 1; i < len + 1; i++) {
            sums[i] = sums[i - 1] + nums[i - 1];
        }

        for (int i = 0; i < len + 1; i++) {
            int right = searchRight(i + 1, len, sums[i] + s, sums);
            if (right == len + 1) {
                break;
            }
            if (res > right - i) {
                res = right - i;
            }
        }
        return res == len + 1 ? 0 : res;
    }

  
    public int searchRight(int left, int right, int key, int sums[]) {
        while (left <= right) {
            int mid = (left + right) / 2;
            if (sums[mid] >= key) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }