编程知识 cdmana.com

Algorithm array series

The largest subarray

1 The sliding window Method solution

letcode 3

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

Example 1:

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

When you encounter characters that are not repeated, go back +1, That new +1 How do you know if the data is the same as the previous element ?( You can't sweep over and over again This string ) Here you can set an array freq[256] Of freq[k] Corresponding to a character ASCII The frequency of the value . If it is 0 There is no repetition

Code :

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int freq[256] = {0}; //256 A place , Initialize to 0
        int l = 0, r = -1;
        int res = 0;

        while(l<s.size()){
            
            if(freq[s[r+1]]==0 && r+1 < s.size())
                freq[s[++r]]++;
            else
                freq[s[l++]]--;
            res = max(res,r-l+1);
        }
        return res;
    }
};

letcode 209

Given a containing n An array of positive integers and a positive integer s , Find the sum of the array ≥ s The smallest length of continuity Subarray , And return its length . If there is no sub array that meets the conditions , return 0.

Example :

Input :s = 7, nums = [2,3,1,2,4,3]
Output :2
explain : Subarray [4,3] Is the smallest subarray in this condition .

Their thinking use How to slide the window

class Solution {
public:
    int minSubArrayLen(int s, vector<int>& nums) {
        int l =0,r = -1;
        int sum = 0;
        int index = nums.size()+1;
        while(l<nums.size()){
            if (r+1<nums.size()&& sum<s){
                sum+=nums[++r];
            }else{
                
            
                sum-=nums[l++];    
            }
            
            if(sum>=s){
                 index = min(index,r-l+1);
            }
            
        }
        if(index == nums.size()+1){
            return 0;
        }
        return index;
    }
};

版权声明
本文为[A strategist who is not good at politics]所创,转载请带上原文链接,感谢

Scroll to Top