少儿编程C++基础：双指针使用总结（三）-成都凡恩机器人联盟

双指针是一种解决问题的技巧或者思维方式，指在访问一个序列中的数据时使用两个指针进行扫描，两个指针可以是同向的，也可以是反向的；我们的关注点可以是这两个指针指向的两个元素本身，也可以是两个指针中间的区域。

滑动窗口基本原理

窗口代表着数组或者序列上的一组元素，用 left 和 right 两个指针分别表示其左右边界，从左到右移动 left 和 right
指针，就像是一个窗口在序列上进行滑动，不断的有新元素从右侧进入窗口，同时有旧的元素从左侧移除窗口，当前窗口内的元素是否满足需求制约着窗口的扩张与收缩。

滑动窗口可以用来解决子串问题。

01、窗口初始化

设置窗口初始化值为 0 ，即 left 和 right 都位于序列的左端位置。

02、窗口扩展

窗口扩张时 left 指针保持不动，向右移动 right 指针；在窗口扩张的初期，窗口右侧纳入新的元素对结果的影响是积极的，有以下两种情况：

①．新加入的元素使窗口得到的结果更优，则每一步都是一个当前最优解；停止扩张的临界条件是新加入的元素刚好使窗口不符合条件。

②．新加入的元素使窗口离达到目标条件更近；停止扩展的临界条件是新加入的元素刚好使窗口符合目标条件。

当窗口达到停止扩张的临界条件时，继续扩张对结果的影响是消极的，此时应该进行窗口收缩。

03、窗口收缩

窗口收缩时 right 指针保持不动，向右移动 left 指针；窗口收缩的初期，窗口左侧丢弃的元素对结果的影响的积极的，有以下两种情况：

①．若窗口停止扩张的临界条件是新加入的元素刚好使窗口不符合目标条件，则丢弃一个旧元素可能使窗口满足条件，停止收缩的临界条件是丢弃一个元素使窗口刚好满足目标条件。

②．若窗口停止扩张的临界条件是新加入的元素刚好使窗口符合目标条件，则丢弃一个旧元素可能使窗口的结果更优，停止收缩的临界条件是丢弃一个元素使窗口刚好不满足目标条件。

当窗口达到停止收缩的临界条件时，继续收缩对结果的影响是消极的，此时应该进行窗口扩张。

04、滑动停止

滑动窗口的过程就是不断的进行窗口扩张与收缩，当窗口扩张对结果的影响是积极时就进行窗口扩张，当窗口收缩对结果的影响时积极时就进行窗口收缩，不断重复这个过程。当right
指针到达序列末尾时，窗口滑动停止。

滑动窗口的应用

01、最小覆盖子串

给你一个字符串 S、一个字符串 T，请在字符串 S 里面找出：包含 T 所有字符的最小子串。示例：输入: S = “DAOBECODEBANC”, T =
“ABC” 输出: “BANC” 说明：如果 S 中不存这样的子串，则返回空字符串 “”。如果 S 中存在这样的子串，我们保证它是唯一的答案。

力扣（LeetCode）第76题

本题中窗口是否满足需求的条件是：窗口中的元素是否包含了目标中所有的字符种类以及对应的个数，本题每次窗口扩张可能达到一个可行解，然后进行窗口收缩优化这个可行解得到最优解，然后扩张窗口寻找下一个可行解。

class Solution {
public:
    
    string minWindow(string s, string t) {
        //特殊的边界处理
        if( s.length() < t.length()) return "";
        if( s.length() == 0) return "";
        if( t.length() == 0) return "";
        
        unordered_map<char,int> need_charmap;//需要寻找的 字符-个数 对应
        for(int i = 0;i < t.length();i++)
        {
            need_charmap[t[i]]++;//初始化need_charmap
        }
        unordered_map<char,int> cur_charmap;//已经找到的 字符-个数 对应
        unordered_set<char> cur_chartype;//已经找齐的字符种类
        int minLeft = 0;//初始化目标窗口左指针为0
        int minLenght = INT_MAX;//初始化满足需要的最小长度为一个绝对最大值，然后不断优化这个值

        int left = 0 ,right = 0;//初始化窗口边界
        while(right < s.length())//窗口滑动停止条件
        {
            char temp = s[right];//本次窗口扩张纳入的新元素
            //更新窗口内元素
            if( need_charmap.find(temp) != need_charmap.end()  ) //新元素是目标字符
            {
                cur_charmap[temp] ++;//已经找到的字符个数+1
                if( cur_charmap[temp] >= need_charmap[temp] )
                {
                    cur_chartype.insert(temp);//标记该类字符已经找齐了
                }
                while( cur_chartype.size() == need_charmap.size())//所有字符种类已经找齐了
                {
                    //记录这个可行解，判断是否最优
                    if( right-left+1 < minLenght)
                    {
                        minLeft = left;
                        minLenght = right-left+1;
                    } 
                    temp = s[left];//本次窗口收缩要丢弃的元素
                    if( need_charmap.find(temp) != need_charmap.end()  ) //是目标字符
                    {
                        cur_charmap[temp] --;
                        if( cur_charmap[temp] < need_charmap[temp] )//数量不够了
                        {
                            cur_chartype.erase(temp);//从找齐的结果中删除这个字符
                        }
                    }
                    left++;//收缩窗口，继续优化这个解
                }     
            }
            right++;//窗口继续扩张，寻找下一个可行解
        }
        return minLenght < INT_MAX ? s.substr(minLeft,minLenght) : "";      
    }
};

02、无重复字符的最长子串

给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。示例 1: 输入: “abcabcbb” 输出: 3 解释: 因为无重复字符的最长子串是
“abc”，所以其长度为 3。

力扣（LeetCode）第3题

本题中窗口是否满足需求的条件是：窗口扩张纳入的新元素和已有元素不重复，本题每次窗口扩张可能都是一个当前最优解，当不符合条件时，收缩窗口使其符合条件，然后扩张窗口寻找下一个最优解。

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        //特殊的边界处理
        if( s.length() == 0) return 0;
        int res = 0;//初始化返回值
        int left = 0,right = 0;//窗口初始化
        unordered_map<char,int> cur_map;
        while( right < s.length())
        {
            char rightStr = s[right];//窗口扩张得到的新元素
            cur_map[rightStr]++;//更新窗口内元素

            if( cur_map[rightStr] == 1)
            {
                res = max(res,right-left+1);//记录最优解
            }
            else//刚好不满足需求时，收缩窗口
            {
                while( cur_map[rightStr] > 1  )
                {
                    char leftChar = s[left];
                    cur_map[leftChar] --;
                    left++;
                }
            }
            right++;
        }
        return res;
    }
};