## 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 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 = {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;
}
};
``````

Scroll to Top