leetcode ---双指针+滑动窗口

阳光穿透心脏的1/2处 2022-08-05 05:05 180阅读 0赞

一：[Minimum Size Subarray Sum][]（最小长度子数组的和O(N)）

题目：

Given an array of n positive integers and a positive integer s, find the minimal length of a subarray of which the sum ≥ s. If there isn't one, return 0 instead.

For example, given the array `[2,3,1,2,4,3]` and `s = 7`,  
the subarray `[4,3]` has the minimal length under the problem constraint.

分析：一开始我采用的是LIS(longest increased sequence)中的最长递增子序列中的动态规划的思想，能通过，但是时间复杂度为O(N

^2)；；；第二种方法是采用双指针+滑动窗口的思想，时间复杂度为O(N)， 严格意义上说是2N，，比如 \[1,2,3,15,3,4,5,15\] s=14,,,只有在15处将前面的元素又重新加了一遍，故为2N

初始快慢指针都为0，fast指针向前移动，当slow和fast中连续字数组的和大于s时，我们就开始缩减窗口，不断的对slow进行向前移动直到sum小于s，然后再移动fast继续循环

代码：

class Solution {
    public:
       // 法一
        /*int minSubArrayLen(int s, vector<int>& nums) {
            int result = nums.size();
            bool flag = false;
            for(int i = 0; i < nums.size(); i++){
                if(nums[i] >= s) return 1;
                int sum = nums[i];
                for(int j = i-1; j >= 0; j--){
                    sum += nums[j];
                    if(sum >= s){
                        result = min(result, i-j+1);
                        flag = true;
                        break;
                    }
                }
            }
            if(flag)return result;
            return 0;
        }*/
        
        int minSubArrayLen(int s, vector<int>& nums) {     // 滑动窗口的形式+双指针
            int result = nums.size()+1;
            int frontPoint = 0, sum = 0;
            for(int i = 0; i < nums.size(); i++){
                sum += nums[i];
                while(sum >= s){    // 找到了窗口
                    result = min(result, i - frontPoint + 1);   // 窗口是否满足要求
                    sum -= nums[frontPoint++];            // 缩减窗口
                }
            }
            return result == (nums.size()+1) ? 0:result;
        }
    };

二：[Minimum Window Substring][]

题目：

Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).

For example,  
S = `"ADOBECODEBANC"`  
T = `"ABC"`

Minimum window is `"BANC"`.

Note:  
If there is no such window in S that covers all characters in T, return the emtpy string `""`.

If there are multiple such windows, you are guaranteed that there will always be only one unique minimum window in S.

分析：这道题刚开始我采用类似于上面滑动窗口的方法，但是每次都要判断当前字符串中是否完全包含字符串t，这个判断就会提升时间复杂度，结果导致TLE。后面参看了discuss中的方法，非常巧妙，也放在这里。代码中map用来存放t字符串中的字符及出现的次数，而window用来存放字符串t中每个字符在字符串s中出现的次数。lettercounts是一个标记变量，当等于t.size()的时候，就表示得到了一个完全包含t的字符子串，然后移动慢指针缩减窗口。

代码：

TLE：

class Solution {
    public:
        bool isContain(const string &sstr, const string &t){
            for(int i = 0; i < t.size(); i++){
                if(sstr.find_first_of(t[i]) == string::npos) return false;
            }
            return true;
        }
        string minWindow(string s, string t) {
            int result = s.size()+1, frontPoint = 0;
            string str="";
            for(int i = 0; i < s.size(); i++){
                while(isContain(s.substr(frontPoint, i-frontPoint+1) , t)){
                    if(result > i-frontPoint+1){
                        result = i-frontPoint+1;
                        str = s.substr(frontPoint, i-frontPoint+1);
                    }
                    frontPoint++;
                }
            }
            return str;
        }
    };

AC代码：

class Solution {
    public:
    
        string minWindow(string s, string t) {
            string result;
            if(s.size() == 0 || t.size() == 0) return result;
            unordered_map<char, int> map;
            unordered_map<char, int> window;  // 滑动窗口
            int lettercounts = 0;               // 标记变量，当等于t.size()的时候，该窗口就是一个完全包含字符串t的子串
            int minLen = s.size()+1;
            
            for(int i = 0; i < t.size(); i++)  // 将t放入map中，就是为了加速
                map[t[i]]++;
                
            for(int fast = 0, slow = 0; fast < s.size(); fast++){  // 快慢指针，快指针不断向前移动，
                char c = s[fast];
                if(map.find(c) != map.end()){      // 
                    window[c]++;
                    if(window[c] <= map[c]){      // 变化lettercount变量
                        lettercounts ++;
                    }
                    if(lettercounts >= t.size()){           // 表示该窗口中已经全部包含t了
                        while(map.find(s[slow]) == map.end() || window[s[slow]] > map[s[slow]]){  // 对窗口进行缩减  1：slow所指向字符不在map中，2：在该子串中                                                                                               //出现很多次  如BBABC    ABC slow指向B
                            window[s[slow]]--;
                            slow++;
                        }
                        if(minLen > fast - slow + 1){    
                            minLen = fast - slow + 1;
                            result = s.substr(slow, minLen);
                        }
                        window[s[slow]]--;     // 缩减窗口
                        slow++;
                        lettercounts --;
                    }
                    
                }
                
            }
            return result;
        }
    };

三：[Contains Duplicate III][]

题目：

Given an array of integers, find out whether there are two distinct indices i and j in the array such that the difference between nums\[i\] and nums\[j\] is at most t and the difference between i and j is at most k.

分析：这道题目也是滑动窗口，滑动窗口一般都是定义一个slow指针，然后一个fast指针不断向前滑动(循环遍历)，这个过程中我们要判断1：是否找到了窗口，2：窗口时否满足要求 3：窗口缩减等

此题也是，设置慢指针l，和快指针i遍历，窗口过大就缩减，判断找到的窗口是否满足要求，技巧是用到了关联容器的lower\_bound函数，如果满足要求就返回true，否则返回false。这里用set或者multiset都一样.。。注意这里的auto是c++11的新特性，可以用来自动类型推断！

class Solution {
    public:
        /*bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
            if(nums.size() < 2 || k == 0) return false;
            multiset<long> windows;       // 滑动窗口
            int l = 0;
            for(int i = 0; i < nums.size(); i++){
                if(i - l > k){     // 窗口大小超过了k 则需要删除nums[l]并且l++
                    windows.erase(nums[l++]);
                }
                auto it = windows.lower_bound((long)nums[i] - (long)t);
                if(it != windows.end() && *it <= ((long)nums[i]+(long)t))    // 用long防止+1溢出
                    return true;
                windows.insert(nums[i]);
            }
            return false;
            
        }*/
        
        bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
            if(nums.size() < 2 || k == 0) return false;
            set<long> windows;       // 滑动窗口
            int l = 0;               // 慢指针
            for(int i = 0; i < nums.size(); i++){
                if(i - l > k){     // 窗口大小超过了k 则需要删除nums[l]并且l++  窗口需要缩减了
                    windows.erase(nums[l++]);
                }
                auto it = windows.lower_bound((long)nums[i] - (long)t);      //  即为nums[i]-t与nums[i]+t之间是否有元素       
                if(it != windows.end() && *it <= ((long)nums[i]+(long)t))    // 用long防止+1溢出  找到了
                    return true;
                windows.insert(nums[i]);             // not found
            }
            return false;
            
        }
    };

[Minimum Size Subarray Sum]: https://leetcode.com/problems/minimum-size-subarray-sum/
[Minimum Window Substring]: https://leetcode.com/problems/minimum-window-substring/
[Contains Duplicate III]: https://leetcode.com/problems/contains-duplicate-iii/