Given an array of n positive integers and a positive integer s, find the smallest contiguous subarray whose sum is greater than or equal to s, and return its length. If no subarray exists, return 0.

Example: input: s = 7, nums = [2,3,1,2,4,3] output: 2 description: the subarray [4,3] is the smallest subarray in this condition.

The violent solution to this problem is, of course, two for loops, and then you keep looking for subsequences that fit, and the time is obviously O(n^2).

The code is as follows:

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
       int result = Integer.MAX_VALUE;
       int sum=0;
       for(int slowIndex=0; slowIndex<nums.length; slowIndex++){ sum=0;for(int fastIndex = slowIndex; fastIndex<nums.length; fastIndex++){ sum = sum + nums[fastIndex];if(sum >= target){
                 int sublength = fastIndex-slowIndex+1;   
                 result = Math.min(result,sublength);
                 break; }}}returnresult == Integer.MAX_VALUE ? 0 : result; }}Copy the code

Time: O(n^2) Space: O(1)

Sliding Windows next introduces another important method for array manipulation: “sliding Windows.”

The so-called sliding window “is constantly adjusting the start and end positions of the sub-sequence to get the result we want”.

S =7 and the array is 2,3,1,2,4,3.

The picture

And then you find 4,3 is the shortest distance.

In fact, from the animation can be found sliding window can also be understood as a double pointer method! However, this solution is more like a window movement, so it is better called sliding window.

In this case, the following three points are determined to achieve sliding Windows:

What’s in the window? How do I move the starting position of the window? How do I move the end of a window? A window is the smallest contiguous subarray whose sum is ≥ s.

How to move the starting position of the window: If the value of the current window is greater than s, the window will move forward (that is, shrink).

How to move the end position of the window: The end position of the window is the pointer to iterate over the array. The start position of the window is set to the start position of the array.

The key to solve the problem is how to move the starting position of the window, as shown in the figure:

The picture

It can be found that “the subtleness of sliding window lies in continuously adjusting the starting position of the subsequence according to the current subsequence and size, thus reducing the violent solution of O(n^2) to O(n).”

Java version code

public class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int result = Integer.MAX_VALUE;
        int sum = 0;
        int slowIndex = 0;
        for (int fastIndex = 0; fastIndex < nums.length; fastIndex++) {
            sum = sum + nums[fastIndex];
            while(sum >= target) { int sublength = fastIndex - slowIndex + 1; result = Math.min(result, sublength); sum = sum - nums[slowIndex]; slowIndex++; }}returnresult == Integer.MAX_VALUE ? 0 : result; }}Copy the code

Time complexity: O(n) Space complexity: O(1)