209. Minimum Size Subarray Sum

四刷 06/2022

Version #2 Sliding Window

Time O(N)

Space O(1)

Runtime: 2 ms, faster than 63.80% of Java online submissions for Minimum Size Subarray Sum.

Memory Usage: 58.4 MB, less than 5.00% of Java online submissions for Minimum Size Subarray Sum.

class Solution {

    public int minSubArrayLen(int target, int[] nums) {

        int minLen = Integer.MAX_VALUE;

        int start = 0; 

        int sum = 0; // subarray [start, end] sum

        for (int end = 0; end < nums.length; end++) {

            sum += nums[end];

            while (start <= end && sum >= target) {

                minLen = Math.min(minLen, end - start + 1);

                sum -= nums[start];

                start++;

            }

        }

        return minLen == Integer.MAX_VALUE ? 0 : minLen;

    }

}

A very good explanation from LeetCode discuss forum
https://discuss.leetcode.com/topic/13749/two-ac-solutions-in-java-with-time-complexity-of-n-and-nlogn-with-explanation

Version #1 Binary Search
Time O(nlogn)

[2ND TRY]
class Solution {
    public int minSubArrayLen(int s, int[] nums) {
// prefixSum[i] -> sum[0, i)
// sum [i, j) -> prefix[j] - prefix[i]
int[] prefixSum = new int[nums.length + 1];
for (int i = 1; i <= nums.length; i++) {
prefixSum[i] = nums[i - 1] + prefixSum[i - 1];
}
int len = Integer.MAX_VALUE;
for (int i = 0; i < nums.length; i++) {
int right = binarySearch(prefixSum, prefixSum[i] + s);
if (right != -1) {
len = Math.min(len, right - i);
}
}
return len == Integer.MAX_VALUE ? 0 : len;
}
private int binarySearch(int[] prefixSum, int target) {
// find the 1st index larger than or equal to target
int start = 0, end = prefixSum.length - 1;
while (start < end) {
int mid = start + (end - start) / 2;
if (prefixSum[mid] >= target) {
end = mid;
} else {
start = mid + 1;
}
}
return prefixSum[start] >= target ? start : -1;
}
}



直接bug free了！ prefix sum的定义是前 i 个数 -> sum[0, i)

14.04 %
class Solution {
    public int minSubArrayLen(int s, int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int len = nums.length;
        int result = Integer.MAX_VALUE;
        // sum[0, i)
        int[] prefixSum = new int[len + 1];
        for (int i = 1; i <= len; i++) {
            prefixSum[i] = prefixSum[i - 1] + nums[i - 1];
        }
        //[2,3,1,2,4,3]
        //[0,2,5,6,8,12,15]
     
        // prefixSum[j] - prefixSum[i] = sum[i, j)
        for (int left = 0; left < len; left++) {
            int right = binarySearch(prefixSum, s + prefixSum[left]);
            if (right != -1) {
                result = Math.min(result, right - left);
            }
        }
        return result == Integer.MAX_VALUE ? 0 : result;
     
    }
    // find the 1st index larger than or equal to target, return -1 if not exist
    private int binarySearch(int[] prefixSum, int target) {
        int start = 0;
        int end = prefixSum.length - 1;
        while (start < end) {
            int mid = start + (end - start) / 2;
            if (prefixSum[mid] < target) {
                start = mid + 1;
            } else {
                end = mid;
            }
        }
        return prefixSum[start] >= target ? start : -1;
    }
}




Version #2 Sliding window with two pointers walking towards the same direction
Two pointers one pass
Time O(n)

[3RD TRY]
class Solution {
    public int minSubArrayLen(int s, int[] nums) {
// sum (i, j]
int i = -1, sum = 0;
int len = Integer.MAX_VALUE;
for (int j = 0; j < nums.length; j++) {
sum += nums[j];
while (i < j && sum >= s) {
len = Math.min(len, j - i);
i++;
sum -= nums[i];
}
}
return len == Integer.MAX_VALUE ? 0 : len;
}
}

二刷
99.97 %
class Solution {
    public int minSubArrayLen(int s, int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        // [left, right]
        int left = 0;
        int right = 0;
        int sum = 0;
        int result = Integer.MAX_VALUE;
        // [2,3,1,2,4,3]
        while (right < nums.length) {
            sum += nums[right];
            while (sum >= s) {
                result = Math.min(result, right - left + 1);
                sum -= nums[left];
                left++;
            }
            right++;
        }
        return result == Integer.MAX_VALUE ? 0 : result;
    }
}

一刷
public class Solution {
    /**
     * @param nums: an array of integers
     * @param s: an integer
     * @return: an integer representing the minimum size of subarray
     */
    public int minimumSize(int[] nums, int s) {
        // write your code here
        if (nums == null || nums.length == 0) return -1;
        int minLength = -1;
        int slow = 0, fast = 0;
        int rangeSum = 0;
        int currLength;
        for (fast = 0; fast < nums.length; fast++) {
            rangeSum += nums[fast];
            while (rangeSum >= s) {
                currLength = fast - slow + 1;
                minLength = minLength == -1 ? currLength : Math.min(currLength, minLength);
                rangeSum -= nums[slow];
                slow++;
            }
            //System.out.println("fast:" + fast + " slow:" + slow + " rangeSum" + rangeSum);
        }
        return minLength;
    }
}