preface

Hello, I'm long Lu. I'm just a junior now. I'm working on the back end and occasionally on the front end. Now the main language is Java. For a long time before, I was learning some technologies of web development. I haven't studied and brushed questions like data structures and algorithms for a long time. I plan to pick them up and learn and do it well during this time.

During this period, I also happened to see that Cao Mao Lufei's blog added a self-study group. I happened to see that the blogger organized a leetcode question swiping and punching activity in the group. I also participated in it for one month. I intend to spend some time doing some questions every day and record them through a blog.

subject

Title source leetcode

leetcode address: 209. Minimum length subarray , difficulty: medium.

Title Description (from leetcode):

Given a n An array of positive integers and a positive integer target . 
Find the array that satisfies its sum ≥ target The smallest continuous subarray of length [numsl, numsl+1, ..., numsr-1, numsr] ，And returns its length. If there is no eligible subarray, 0 is returned.

Example 1:
Input: target = 7, nums = [2,3,1,2,4,3]
Output: 2
 Explanation: subarray [4,3] Is the subarray with the smallest length under this condition.

Example 2:
Input: target = 4, nums = [1,4,4]
Output: 1

Example 3:
Input: target = 11, nums = [1,1,1,1,1,1,1,1]
Output: 0

Local debug code:

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        ...
    }

    public static void main(String[] args) {
        int[] nums = new int[]{2,3,1,2,4,3};
        System.out.println(new Solution().minSubArrayLen(7, nums));
    }
}

Problem solution

NO1. Violence Act (O(n2))

At the beginning, there was no idea. It was solved directly by using violent methods.

Idea: in the process of traversing the array, find the subarray with the smallest length every time you reach an index position. Each time you find the smallest subarray, compare it with the smallest decimal (continuous number) temporarily saved.

Code: time complexity: O(n2), actually n+(n-1)+(n-2)..., it is difficult to find the specific time complexity

public int minSubArrayLen(int target, int[] nums) {
    if (nums.length == 0 || nums == null) {
        return 0;
    }
    int minSize = nums.length + 1;
    for (int i = 0; i < nums.length; i++) {
        int num = 0;
        //Get the minimum value from the current index position and get the minimum length that meets the conditions
        for (int j = i; j < nums.length; j++) {
            num+=nums[j];
            if(num>=target){
                minSize = Math.min((j - i + 1), minSize); //(j-i+1)<minSize?(j-i+1):minSize => Math.min((j - i + 1), minSize)
                break;
            }
        }
    }
    return minSize == nums.length + 1 ? 0 : minSize;//Judge whether it is consistent with the initial value. If it is consistent, it means that the matching minimum sub array is not found
}

No2: sliding window (O(n))

Idea: see details Code capriccio-209. Subarray with the smallest length

Two pointers are needed to cooperate. The core is to move the values and in the pointer range. Can No1 A large number of unnecessary situations in problem solving are eliminated to improve efficiency.
The left pointer uses a variable 0 as the initial value; The right pointer uses the index of the traversal array i
	First, traverse and continuously move the right pointer to a position that meets the conditions(>=target)，Then start reducing the scope to>=target Start moving the left pointer for the condition, once<target It shows that the reduced range is enough. Then you need to move the right pointer back to find other smaller situations. Moving and screening through the left and right pointers is much better than the previous violence method!

Code: time complexity O(n).

• The while in the for loop will not be executed many times each time. Generally, the sum of 1-3 times and the original for loop times is O(2n), which can be directly regarded as O(n).

public int minSubArrayLen(int target, int[] nums) {
    if (nums.length == 0 || nums == null) {
        return 0;
    }
    int minSubLen = nums.length+1;//Maximum quantity
    int leftCur = 0; //Left pointer
    int sum = 0;//Used to record the value in the current pointer interval
    for (int i = 0; i < nums.length; i++) {  //i is equivalent to the right pointer
        sum += nums[i];
        while(sum>=target){   //It is used to move the left pointer and reduce the inter cell range in order to meet other conditions in the future, such as sum > = target
            int subLen = i - leftCur + 1;  //Calculate current interval quantity
            minSubLen = Math.min(subLen, minSubLen);//The minimum number of intervals is obtained by comparing with the previous interval
            sum -= nums[leftCur++];//Interval reduction
        }
    }
    return minSubLen == nums.length + 1 ? 0 : minSubLen;
}

reference material

[1]. leetcode problem solving

[2]. Code Capriccio leetcode brush questions - two point search question solution

I am a long way. Thank you for your patience in reading. If you have any questions, please point them out and I will actively adopt them!
Welcome to my official account, long road Java, sharing Java learning articles and related materials.
Q group: 851968786 we can discuss and study together
Note: it can be reproduced, and the article link needs to be attached