Technology Sharing

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

1. The subarray with the smallest length

Leetcode 209. The subarray with the smallest length

When you see this topic, the first thing that comes to mind is brute force enumeration, so let's try enumerating the following:

Obviously, the brute force approach will time out.

Is there any way to optimize it so that it does not time out? Let's analyze it:

In the brute force enumeration, our right will return to the next left position each time, and then re-enumerate with the left.

The specific steps for optimizing enumeration are as follows:

In the above enumeration process, our blue box is like a sliding window of variable size. We call this methodSliding Window

For sliding windows, there are only a few steps:

The starting and update result positions of each question window are not fixed, and should be analyzed based on specific circumstances.

According to the sliding window method, our code will not time out.

A simple analysis of the following time complexity: From the code it seems to be O(n²), but due to our sliding window idea, the two pointers are traversed in the same direction and will not go back; when the right pointer ends, the loop ends, so itsThe time complexity is O(n).

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int ret = INT_MAX;
        int n = nums.size();
        int sum = 0;
        for(int left = 0, right = 0; right < n; right++)//right后移
        {
            //进窗口
            sum += nums[right];
            //判断窗口
            while(sum >= target)
            {
                //符合条件，更新结果
                ret = min(ret,right - left + 1);
                sum -= nums[left];//出窗口
                left++;
            }  
        }
        if(ret == INT_MAX)
            return 0;
        else
            return ret;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

2. The longest substring without repeated characters

Leetcode 3. The longest string without repeated characters

The first method that comes to mind for this problem is undoubtedly enumeration, and then count the number of times each character appears; if a character appears twice, then the string corresponding to the current character is the longest substring

We found that brute force enumeration can also pass

Is there a better solution? Let's analyze it.

Isn’t the above solution just a sliding window?

Is the time complexity of O(n) better than brute force enumeration O(n)?²) is even better

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int n = s.size();
        int hash[128] = { 0 };
        int ret = 0;
        for(int left = 0, right = 0; right < n; right++)
        {
            hash[s[right]]++;//入窗口，先记录当前
            while(hash[s[right]] > 1)//若s[right]重复
            {
                hash[s[left]]--;//出窗口
                left++;
            }
            ret = max(ret,right - left + 1);//更新结果
        }
        return ret;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

3. Maximum number of consecutive 1s III

Leetcode 1004. Maximum number of consecutive 1s III

Analyzing the topic, we can see thatThe meaning of 0 being flipped is: 0 can be used as 1Our goal is to find an interval with the largest number of consecutive 1s, where the number of 0s cannot exceed k.

The brute force enumeration method for this problem will not be demonstrated, we will go directly to the sliding window.


This way our code will pass.

class Solution {
public:
    int longestOnes(vector<int>& nums, int k) {
        int n = nums.size();
        int zero = 0;//统计0的个数
        int ret = 0;
        for(int left = 0, right = 0; right < n; right++)
        {
            //进窗口，判断是否是0
            if(nums[right] == 0)
                zero++;
            //判断0的个数是否大于k
            while(zero > k)
            {
                //判断是否是0出窗口
                if(nums[left] == 0)
                    zero--;
                left++;
            }
            //更新结果
            ret = max(ret,right-left+1);
        }
        return ret;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

4. Minimum number of operations to reduce x to 0

Leetcode 1658. Minimum number of operations to reduce x to 0

By reading the question, we can find that it is sometimes on the left and sometimes on the right. Isn’t it difficult to control? So what should we do?
When the right thing is difficult, the opposite happens

• We find a continuous interval in the array, remove the contents of the continuous interval from the array, and when the remaining content is exactly equal to x, then we have found a situation
• This continuous interval isThe sum of the elements in the array minus x
• When we find the longest contiguous block in the array, we have found the optimal solution.

Just like the previous question, use a sliding window.

class Solution {
public:
    int minOperations(vector<int>& nums, int x) {
        int ret = 0;
        int total = 0;
        int n = nums.size();
        for(auto e : nums)
            total += e; //求数组的和
        int target = total - x; //target为要找的连续区间的总大小

        if(target < 0)//细节
            return -1;
        if(total == x)
            return n;
            
        int sum = 0;
        for(int left = 0, right = 0; right < n; right++)
        {
            sum += nums[right];//进窗口
            while(sum > target)
            {
                sum -= nums[left];
                left++;
            }
            if(sum == target)//找到目标区间，取长的一个
                ret = max(ret,right - left + 1);
        }
        if(ret == 0)
            return -1;
        else
            return n - ret;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

5. Fruit basket

Leetcode 904. Fruits in a basket

This title is so long, what does it mean?

There are only two baskets, there can be only two kinds of fruits in the baskets, and you cannot cross trees. What is the maximum number of trees you can pass through?
Then we need to find the length of a continuous interval. We can use a sliding window

How do I know how many fruits are currently picked? ----Use hash table statistics

We can find that the consumption of using hash tables is still quite large. Can it be optimized further?

According to the requirements of the question, the number of types is less than 10⁵So we can directly use an array + a variable (record type)

This greatly improves our efficiency.

class Solution {
public:
    int totalFruit(vector<int>& fruits) {
        int n = fruits.size();
        int ret = 0;
        int hash[100000] = { 0 };
        int kinds = 0;
        for(int left = 0, right = 0; right < n; right++)
        {
            if(hash[fruits[right]] == 0)//判断是否是新种类水果
                kinds++;

            hash[fruits[right]]++;//进窗口
            
            while(kinds > 2)//判断总类是否大于2
            {
                hash[fruits[left]]--;//出窗口
                if(hash[fruits[left]] == 0)
                    kinds--;  //去除该种类
                left++;
            }
            ret = max(ret,right - left + 1);
        }
        return ret;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

6. Find all anagrams in a string

Leetcode 438. Find all anagrams in a string

Analyzing the question, we can see that it is to find the p string in the s string (the order of characters in the p string can be shuffled).
Then we canFind a substring with the same length as p and the same character type and number as p.。

So we can use two hash tables to count the types and numbers of characters in the p string and s string respectively.

Let's try using brute force enumeration:

How are the two hash tables compared?

1. First, use hash1 to record the number of character types in string p
2. Traverse s and find a substring with the same length as p. At the same time, hash2 stores the current character.
   a. If hash2[right] <= hash1[right], the number of “valid characters” increases
   b. If hash2[right] > hash2[right], the type of "valid character" remains unchanged

The brute force enumeration method can indeed pass, but the efficiency is relatively low.
Since we are looking for a continuous interval, can we use a sliding window? Let's try it.

This way our efficiency will be much higher.

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        vector<int> ret;
        int len = p.size();
        int hash1[128] = { 0 };
        for(auto e: p)
            hash1[e]++;//统计p串的种类
        int n = s.size();
        int hash2[128] = { 0 };//统计子串种类
        int kinds = 0;
        int tmp = 0;
        for(int left = 0,right = 0; right < n ; right++)
        {
            hash2[s[right]]++; //进窗口
            tmp++;//子串长度增加
            if(hash2[s[right]] <= hash1[s[right]])
                kinds++;//"有效字符"种类增加
            if(tmp > len)
            {
                if(hash2[s[left]] <= hash1[s[left]])
                    kinds--;//left位置为“有效字符”，种类减少
                hash2[s[left]]--;
                tmp--;
                left++;
            }
            if(tmp == len)
                if(kinds == len)
                    ret.push_back(left);
        }
        return ret;
        
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

7. Concatenate all substrings of a word

Leetcode 30. Concatenate all substrings of a word

This question is similar to the previous one, except that the characters are replaced with strings. Therefore, we still use the sliding window + hash table method to solve it.

Steps to solve the problem:

1. First use hash1 to count the types of strings in words
2. Use a sliding window (since the length of the string is fixed, you can jump the length directly)
   a. Define the start: left, right
   b. When a string enters the window, it needs to be trimmed using the string function substr
   c. Determine the type of string
   Is it out of window?
   Update results

However, only a part of the code has been analyzed. After analyzing its test cases, we find that

This way the code passes!

class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        vector<int> ret;
        unordered_map<string,int> hash1;
        for(auto& e : words)
            hash1[e]++;//统计要求的字符串种类
        int n = s.size();
        int len = words[0].size();//固定的字符串长度
        int m = words.size();//数组长度
        for(int i=0; i < len; i++)
        {
            unordered_map<string,int> hash2;
            int count = 0;
            for(int left = i, right = i; right <= n -len; right+= len)
            {
                string in = s.substr(right,len);//裁剪字符串
                hash2[in]++;//进窗口
                if(hash2[in] <= hash1[in])
                    count++;//统计当前字符串数量
                if(right - left + 1 > m*len)//判断字符串数量是否大于字符数组
                {
                    string out = s.substr(left,len);
                    if(hash2[out] <= hash1[out])
                        count--;
                    hash2[out]--;//出窗口
                    left += len;
                }
                if(count == m)
                    ret.push_back(left);
            }
        }
        return ret;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

8. Minimum Covering Substring

Leetcode 76. Minimum covering substring

The solution to this problem is similar to the previous one, which is to find all the characters of string t in string s, but here we need to return the smallest one found.

We still use the sliding window + hash table method to solve it.

1. Use hash1 to count the types and number of characters in string t
2. Sliding window: define the starting position left, right
   a. Enter the window
   b. Determine whether to exit the window
   c. Update the result (only need to record the starting position and length of the string, and finally cut the substring)

Just record the starting position and length of the string in the code, and our code will pass.

class Solution {
public:
    string minWindow(string s, string t) {
        int hash1[128] = { 0 };
        for(auto e : t)
            hash1[e]++;//统计t串的字符种类和数量
        int m = t.size();
        int n = s.size();
        int hash2[128] = { 0 };
        int count = 0;
        int start = 0;
        int len = INT_MAX;
        for(int left = 0, right = 0; right < n; right++)
        {
            hash2[s[right]]++;//进窗口
            if(hash2[s[right]] <= hash1[s[right]])//是否更新有效字符
                count++;
            while(count >= m)//是否出窗口
            {
                if(count == m)//找到符合种类的子串
                {
                    //取长度小的一个
                    int curlen = right - left + 1;
                    if(curlen < len)
                    {
                        start = left;
                        len = curlen;
                    }
                }
                //出窗口
                if(hash2[s[left]] <= hash1[s[left]])
                    count--;
                hash2[s[left]]--;
                left++;
            }
        }
        if(len == INT_MAX)
            return "";
        else
            return s.substr(start,len);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42