[leetcode sliding window problem]

Every day I don't dance , It's all a betrayal of life .

Leetcode.3 Longest substring without repeating characters

Given a string s , Please find out that there are no duplicate characters in it Longest substrings The length of .

Example 1:

Input : s = “abcabcbb”
Output : 3
explain : Because the longest substring without repeating characters is “abc”, So its length is 3.

Example 2:

Input : s = “bbbbb”
Output : 1
explain : Because the longest substring without repeating characters is “b”, So its length is 1.

Example 3:

Input : s = “pwwkew”
Output : 3
explain : Because the longest substring without repeating characters is “wke”, So its length is 3.
Please note that , Your answer must be Substring The length of ,“pwke” Is a subsequence , Not substring .

Tips ：

• 0 <= s.length <= 5 * 104
• s By the English letters 、 Numbers 、 Symbols and spaces

source ： Power button （LeetCode）
link : Am I

solution 1： Violent solution

Ideas ：

• Generate substrings one by one
• See if it doesn't contain duplicate characters
• Time complexity O(N²)
• namely ：

• 1. Define a right=0： In the outer circle right Represents traversal string , Find the length
• 2. Define a left=0： In the inner circle left Indicates that the judgment is from the starting position to right Is there a repeating element , If yes, stop the cycle and change the starting condition , namely left The internal circulation of plays a judgment role .
• 3. Define a cur, Express left Starting conditions for , Because if there are repeated characters , Because of the left The corresponding element is the same as right The corresponding elements are the same as , We should let cur = left+1, Skip this repeated character and start traversing .
• 4. Define a count Temporary variables , Define a max Record the largest count.

int lengthOfLongestSubstring(char* s)
{
    
    if (s == NULL)
    {
    
        return 0;
    }
    int left = 0;
    int right = 0;
    int max = 0;
    int count = 0;
    int cur = 0;       // When there are repeating elements , location left Starting position 
    int len = strlen(s);
    for (; right < len; right++)  //o（n） Loop through the string 
    {
    
        count = 0;
        for (left = cur; left <= right; left++)  //right Every time you move ,left Just cycle through it and check if there are duplicate elements 
        {
    
            count++;    // Check whether there are repeated elements every time , Count them all .
            if (s[left] == s[right] && left != right) // When the same element appears , Two cases , A kind of left==right, Don't deal with it .left It's not equal to right There are repeating elements ,cur = left+1, Give Way left The next cycle starts by skipping the repeating elements 
            {
    
                cur = left + 1;
                break;
            }
        }
        if (count > max)
        {
    
            max = count;
        }
    }
    return max;
}

solution 2： The sliding window + Hash

Ideas ：

• Repeat characters --> once
• Once the number of times is involved , Hash save
• When constructing a substring, the record length uses a sliding window

1. Definition left,right For the left and right boundaries of the sliding window
2. Definition hash[127], The size of the array is larger than that of the largest character ascii The code value should be large
3. Definition max Record right-left The maximum of

There are two cases when traversing ：

1. s[right] Recurring ：

• 1. hash Get rid of left
• 2. left+=1
• 3. to update max

2. s[right] It didn't show up ：

• 1. hash add right
• 2. right+=1
• 3. to update max

int lengthOfLongestSubstring(char* s) {
    
    
    int hash[127] = {
     0 };
    int left = 0;
    int right = 0;
    int max = 0;

    while (s[right]) {
    
        if (hash[s[right]]) {
    
            hash[s[left]] -= 1;
            left += 1;
        }
        else {
    
            hash[s[right]] += 1;
            right += 1;
        }
        max = max < (right - left) ? (right - left) : max;
    }
    return max;
}

Leetcode.209 Subarray with the smallest length

Given a containing n An array of positive integers and a positive integer target .

Find the sum of the array ≥ target The smallest length of Continuous subarray [numsl, numsl+1, …, numsr-1, numsr] , And return its length . If there is no sub array that meets the conditions , return 0 .

Example 1：

Input ：target = 7, nums = [2,3,1,2,4,3]
Output ：2
explain ： Subarray [4,3] Is the smallest subarray in 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

Tips ：

• 1 <= target <= 109
  1 <= nums.length <= 105
  1 <= nums[i] <= 105

source ： Power button （LeetCode）
link : Am I

solution 1： Violent solution （ Will exceed the time limit ）

That is, traverse all possible substrings , The time complexity is O(N²)

int minSubArrayLen(int target, int* nums, int numsSize) {
    
    int i = 0;
    int j = 0;
    int sum = 0;
    int min = INT_MAX;
    for (i = 0; i < numsSize; i++)
    {
    
        sum = 0;
        for (j = i; j < numsSize; j++)
        {
    
            sum += nums[j];
            if (sum >= target)
            {
    
                min = fmin(min, j - i + 1);
                break;
            }
        }

    }
    if (min == INT_MAX)
        return 0;
    return min;

}

solution 2： The sliding window

Ideas ：

1. Definition [start,end] Is the sliding window interval
2. Definition ans =INT_MAX, Record the length of the element that meets the condition
3. Definition sum Is the sum within the sliding range

Define the boundary of a window [start,end],end Keep moving to the right ,sum Is the sum of elements in this range , When more than target when , Save it to the return value , And the left side of the window starts to slide to the right , With the sliding process , The value on the left that is not included in the window interval needs to be subtracted , meanwhile start++, Until sum<target until .

int minSubArrayLen(int target, int* nums, int numsSize){
    
    int start = 0;
    int end = 0;
    int ans = INT_MAX;
    int sum = 0;
    while(end<numsSize)
    {
    
        sum+=nums[end];
        while(sum>=target)// no need if The reason is that the number on the right side may be too large, resulting in subtracting a number on the left sum Still greater than target
        {
    
            ans = fmin(ans,end-start+1);
            sum-=nums[start];
            start++;
        }
        end++;
    }
    return ans == INT_MAX? 0 : ans;
}

summary ：

Guys, this is a new column for topic brushing , Here we will continue to share useful experiences and methods in the future , If it helps you , Don't forget the support of the third company ！