双指针

含义

双指针是用两个下标来遍历数组或者链表这两种数据结构的算法技巧
使用双指针，需要规定好移动的策略

类别

快慢指针

快慢指针的一般用法是来判断该链表是否存在回路，拓展到图的数据结构时，当图采用邻接表，如std::vector<std::list> adjList来存储的时候，可以判断是否有环

滑动窗口

滑动窗口是使用一个指针定为一个起点，另一个指针来移动。这里的双指针位置可以是同一个起点，或者一个在开头一个在结尾，用双指针来定位一个矩形区域；或者使用容器deque来维持一个双端队列，这个队列存储的元素是该滑动窗口的值

一些经典问题

接雨水
分析
对于收集雨水的总和，可以分解成每个位置雨水的总和，那么就应该分析每个位置接雨水的计算方法，经分析：每个位置雨水量=min(左侧最大高度，右侧最大高度) – 当前高度
原始方法-动态规划
那么就应该遍历每个位置，对于每个位置的左侧和右侧进行单调分析，左侧应该是从当前位置向左应该递增，右侧应该是从当前位置向右递增，此时的时间复杂度最坏情况是O(n²)

int trap(vector<int>& height) {
        int n = height.size();
        if(n == 0) return 0;
        vector<int> leftMax(n);
        vector<int> rightMax(n);
        leftMax[0] = height[0];
        for(int i = 1 ; i < n ; i ++){
            leftMax[i] = max(height[i],leftMax[i-1]);
        }
        rightMax[n-1] = height[n-1];
        for(int i = n - 2 ; i >= 0 ; i --){
            rightMax[i] = max(height[i],rightMax[i+1]);
        }
        int water = 0;
        for(int i = 0 ; i < n ; i ++){
            water += min(leftMax[i],rightMax[i]) - height[i];
        }
        return water;
    }

优化方法 – 双指针
优化核心方向：如何在不存储完整数组的情况下，正确的知道每个位置的左右最大高度？
所以可以使用双指针的O(1)的空间复杂度来避免使用O(n)的空间

如何确保正确：需要双指针规定双指针的移动策略：总是移动较小的一侧指针（较小的一侧必定保证该位置是能够存储水的），在移动的过程中动态更新最大高度

int trap(vector<int>& height) {
        int left = 0 , right = height.size() - 1;
        int leftMax = 0 , rightMax = 0;
        int water = 0;
        while(left < right)
        {
            if(height[left] < height[right])
            {
                if(height[left] < leftMax){
                    water += (leftMax - height[left]);
                }else{
                    leftMax = height[left];
                }
                left++;
            }else{
                if(height[right] < rightMax){
                    water += (rightMax- height[right]);
                }else{
                    rightMax = height[right];
                }
                right--;
            }
        }
        return water;
    }

滑动窗口最大值
滑动窗口 – 双端队列
使用deque来维持该滑动窗口的形态和单调性，该双端队列存储的是数组的下标，从而建立了双端队列和数组的联系，之后让双端队列的队首一直是该滑动窗口的最大值，从而存储结果的时候就取出队首元素，获取数组中的值，存储到目标中

vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        vector<int> res;
        // 存储下标，保证双端队列的队首是该滑动窗口的最大值
        deque<int> dq;
        for(int i = 0 ; i < nums.size() ; i ++)
        {
            while(!dq.empty() && nums[dq.back()] < nums[i]) dq.pop_back();
            while(!dq.empty() && dq.front() <= i - k) dq.pop_front();
            dq.push_back(i);
            if(i >= k - 1)res.push_back(nums[dq.front()]);
        }
        return res;
    }

最小覆盖子串
使用两个哈希表和一个表示已经匹配数量的整数来判断是否是最小覆盖子串，使用双指针来遍历整个字符串，此次的双指针的起点都是相同的

 string minWindow(string s, string t) {
        string res;
        if (t.empty() || s.empty() || t.size() > s.size()) return res;
        unordered_map<char,int> need,window;
        for(char c : t) need[c] ++;

        int left = 0 , right = 0;
        int valid = 0;
        int start = 0 , len = INT_MAX;

        while(right < s.size())
        {
            char c = s[right];
            right++;

            if(need.count(c)){
                window[c]++;
                if(window[c] == need[c]) valid++;
            }

            while(valid == need.size()){
                if(right - left < len){
                    start = left;
                    len = right - left;
                }
                char d = s[left];
                left++;
                if(need.count(d)){
                    if(window[d] == need[d]) valid--;
                    window[d]--;
                }
            }
        }
        return len == INT_MAX ? "" : s.substr(start,len);
    }