Subarray_1

Question

Given an integer array nums and an integer k, return the length of the shortest non-empty subarray of nums with a sum of at least k. If there is no such subarray, return -1. All the number is positive.

A subarray is a contiguous part of an array.

Example 1:

Input: nums = [1], k = 1
Output: 1

Example 2:

Input: nums = [1,2], k = 4
Output: -1

Example 3:

Input: nums = [2,1,2], k = 3
Output: 3

Constraints:

• 1 <= nums.length <= 10^5

• -10^5 <= nums[i] <= 10^5

• 1 <= k <= 10^9

• Solution1 brute force

Step 1: analyze the question

[1, 2, 3, 4, 5, 6]

[start, end], sum -> time complexity: O(n^3) space complexity: O(1)

class Solution {
    public int shortestSubarray(int[] nums, int k) {
        int n = nums.length;
        int minLength = Integer.MAX_VALUE;
        for (int start = 0; start < n; start++) {
            for (int end = start; end < n; end++) {
                int sumOfSubarray = 0;
                for (int i = 0; i <= end; i++) {
                    sumOfSubarray += nums[i];
                }
                //subarray 的加和的边界
                if (sumOfSubarray >= k) {
                    minLength = Math.min(minLength, end - start + 1);
                }
            }
        }
        if (minLength == Integer.MAX_VALUE) {
            return -1;
        }
        return minLength;
    }
}

• Solution2 prefix sum

Step 1: analyze the question

[1, 2, 3, 4, 5, 6]

[0, 1, 2, 3, 4, 5, 6] sum from index 0 -> i, length = nums.length + 1

[start, end], sum -> prefixSum[end + 1] - prefixSum[start]

time complexity: O(n^2) space complexity: O(n)

class Solution {
    public int shortestSubarray(int[] nums, int k) {
        int n = nums.length;
        int minLength = Integer.MAX_VALUE;
        int[] prefixSum = getPrefixSum(nums);
        for (int start = 0; start < n; start++) {
            for (int end = start; end < n; end++) {
                if (prefixSum[end + 1] - prefixSum[start] >= k) {
                    minLength = Math.min(minLength, end - start + 1);
                }
            }
        }
        if (minLength == Integer.MAX_VALUE) {
            return -1;
        }
        return minLength;
    }
    //prefixSum 的构建
    private int[] getPrefixSum(int[] nums) {
        int[] prefixSum = new int[nums.length + 1];
        for (int i = 1; i <= nums.length; i++) {
            prefixSum[i] = prefixSum[i - 1] + nums[i - 1];
        }
        return prefixSum;
    }
}

• Solution3 prefix sum + binary search(not work on this question, because the number could be negative)

Step 1: analyze the question

[1, 2, 3, 4, 5, 6]

[0, 1, 2, 3, 4, 5, 6] sum from index 0 -> i, length = nums.length + 1

[start, end], sum -> prefixSum[end + 1] - prefixSum[start]

fix start, use binary search to find end

time complexity: O(nlogn) space complexity: O(n)

class Solution {
    public int shortestSubarray(int[] nums, int k) {
        int n = nums.length;
        int minLength = Integer.MAX_VALUE;
        int[] prefixSum = getPrefixSum(nums);
        for (int start = 0; start < n; start++) {
            int end = getEndOfSubarray(prefixSum, start, k);
            if (prefixSum[end + 1] - prefixSum[start] >= k) {
                minLength = Math.min(minLength, end - start + 1);
            }
        }
        if (minLength == Integer.MAX_VALUE) {
            return -1;
        }
        return minLength;
    }
    private int[] getPrefixSum(int[] nums) {
        int[] prefixSum = new int[nums.length + 1];
        for (int i = 1; i <= nums.length; i++) {
            prefixSum[i] = prefixSum[i - 1] + nums[i - 1];
        }
        return prefixSum;
    }
    private int getEndOfSubarray(int[] prefixSum, int start, int k) {
        int left = start, right = prefixSum.length - 2;
        while (left + 1 < right) {
            int mid = left + (right - left) / 2;
            if (prefixSum[mid + 1] - prefixSum[start] >= k) {
                right = mid;
            }
            else {
                left = mid;
            }
        }
        if (prefixSum[left + 1] - prefixSum[start] >= k) {
            return left;
        }
        return right;
    }
}

• Solution4 two point

Step 1: analyze the question

[1, 2, 3, 4, 5, 6]

i, j two point

i,j -> 0

j++ -> sum>=k

i++ until sum < k, minLength

time complexity: O(n) space complexity: O(1)

class Solution {
    public int shortestSubarray(int[] nums, int k) {
        if (nums == null || nums.length == 0) {
            return -1;
        }
        int n = nums.length;
        int minLength = Integer.MAX_VALUE;
        int sumOfSubarray = 0;
        int j = 0;
        for (int i = 0; i < n; i++) {
            while (j < n && sumOfSubarray < k) {
                sumOfSubarray += nums[j];
                j++;
            }
            if (sumOfSubarray >= k) {
                minLength = Math.min(minLength, j - i);
            }
            sumOfSubarray -= nums[i];
        }
        if (minLength == Integer.MAX_VALUE) {
            return -1;
        }
        return minLength;
    }
}