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

Brutal force

Use backtracking to try every possible subarray. O(n!) complexity.

Can we do better?

Two pointer

Use a end pointer to indicate the end index for the subarray; initially start is 0, if the sum of subarray is larger than s, gradually increase the start to make the subarray shorter. The end will traverse through the array giving out every possible subarray.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int start = 0, end = 0, sum = 0; // sum is the sum of subarray
// initialize the size of minimum subarray as max value
int min = Integer.MAX_VALUE;
while (end < nums.length) {
    sum += nums[end];
    end++;
    while (sum >= s) {
    // if sum is larger than s, it's possible to "squeze" space of the subarray, hence, increase the start index
        min = Math.min(min, end - start); // no doubt there is a min
        sum -= nums[start];
        start++;
    }
}
return min == Integer.MAX_VALUE ? 0 : min; 
// if min is unchanged, then there's no such subarray such that sum >= s

Thought about two pointers

Two pointers method is such a beautiful and elegant solution for many questions, however it is hard to come up with.

Basically, max, min subarray problem can be solved by two pointers each points to the start and end subarray.