数组双指针——左右指针

双指针操作时候left=0,right=s.size()-1，注意指针越界问题，判断时候有短路问题，先验边界！
两端向中间

n数之和

两数之和：先排序，再双指针，扫的时候左右指针跳过重复元素，代码写法固定，分三种情况，用while跳过重复元素
三数之和：避免重复的关键点在于，不能让第一个数重复，至于后面的两个数，我们复用的 twoSumTarget 函数会保证它们不重复。所以代码中必须用一个 while 循环来保证 3Sum 中第一个元素不重复。

有序数组的平方

-4 0 12 15 按平方大小重排
思路：两个指针分别指向数组的两端，比较两端元素的平方大小，将较大的平方放到结果数组的末尾，并移动对应的指针，直到两个指针相遇。

回文串相关

中间向两端（最长回文子串）
遍历每一个“中心”向外扩散（从一个中心扩散或者两个中心扩散）

1
2
3
for 0 <= i < len(s):
    找到以 s[i] 为中心的回文串
    更新答案

二分查找

数组有序就考虑

找一个元素

左闭右开区间[left, right)

  • while(left < right) 因为当left == right时，区间已经没有元素了，可以跳出

  • left = mid + 1; left所指的元素还要再找，所以指向跳过mid这个元素的位置

  • right = mid; right所指向的mid刚好不用再找

    while(left < right){
    int mid = left + (right - left) / 2;
    if(nums[mid] == target) return mid;
    else if(nums[mid] < target) left = mid + 1;
    else right = mid;
    }
    return -1; // not found

}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

## 颜色分类（荷兰国旗问题）

三指针，分别指向0的右边界、当前元素、2的左边界，遍历数组
如果是 0：与 nums[low] 交换，low++、mid++（新交换进来的元素已处理为 0 或 1）。
如果是 1：mid++（跳过）。
如果是 2：与 nums[high] 交换，high--（交换进来的元素必须再次检查，因此不移动 mid）。

```C++
void sortColors(vector<int>& nums) {
  int left = 0, right = nums.size() - 1;
  int i = 0;
  while(i <= right) {
    if(nums[i] == 0) {
      swap(nums[left++], nums[i++]);
    } else if(nums[i] == 2) {
      swap(nums[right--], nums[i]);
    } else {
      i++;
    }
  }
}

数组双指针——快慢指针

去重/删除/移动元素

一个慢指针用来写，一个快指针用来在前面扫

1
2
3
4
5
6
7
8
int slow = 0, fast = 0;
while(fast < nums.size()){
    if(nums[fast] != nums[slow]){
        slow++;
        nums[slow] = nums[fast];
    }
    fast++;
}

滑动窗口（重点）

注意：可以滑动固定大小的窗口，维护数据和答案！
用int，unordered_map，set等维护窗口内数据
同样用左闭右开区间。slow fast指针不回退，所以只用O(n)扫一遍数组，O(n2)全遍历的部分情况不用扫
外循环更新right，内循环更新left，[left,right)左闭右开区间

核心还是思考 什么时候收缩窗口？什么时候更新答案？（注意伸缩窗口可能要维护一些数据）

求最长：不断加入right，while(窗口不合法)时才收缩，收缩到符合条件出while循环，更新答案，因为此时窗口刚刚恢复合法。

1
2
3
4
5
6
7
8
9
10
11
12
13
for (int right = 0; right < n; ) {
        // 1. 进：加入右边界
        window[s[right]]++;
        right++;
        // 2. 屈：当窗口不合法（例如有重复字符）时，收缩左边界
        while (window[s[right]] > 1) { 
            window[s[left]]--;
            left++;
        }

        // 3. 伸：此时窗口一定合法，更新最大值 是以right为右的最长子串（包括子数组的计数为right-left）
        ans = std::max(ans, right - left);
}

求最短：不断加入right，while(窗口合法)时收缩left，尝试找到更短的答案，收缩到不合法出while循环，在while内更新答案，因为while内部窗口是合法的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
for (int right = 0; right < n; ) {
        // 1. 进：加入右边界
        sum += nums[right++];

        // 2. 屈：只要窗口满足条件（合法），就不断尝试收缩
        while (sum >= target) {
            // 3. 算：在收缩过程中更新最小值
            ans = std::min(ans, right - left );
            
            // 移除左边界，看剩下的是否依然满足条件
            sum -= nums[left];
            left++;
        }
    }

计数：在最长修正出一个满足条件的以right为右的最长子串，计数+=right-left(都以right为右边界)

通用外层框架

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 滑动窗口算法框架伪码
int left = 0, right = 0;

while (right < nums.size()) {
    // 右移增大窗口
    window.addLast(nums[right]);
    right++;
    
    while (window needs shrink) { // ?
        
        // 缩小窗口
        window.removeFirst(nums[left]);
        left++;
    }
}

习题

Leetcode 76. 最小覆盖子串
维护need，window两个unordered_map哈希表，字符移入移出时更新window，当某个字符是need所需且符合/不符合数量时更新valid，valid == need.size()时说明窗口已经覆盖了need，进入内循环更新结果并缩小窗口

1
2
unordered_map<char, int> need, window;
if(need.count(c)) // 判断c是否在need中

Leetcode 713. 乘积小于K的子数组
计数：以right为右边界开区间的满足条件的子数组个数是right-left（包括单元素子数组）

Leetcode 424. 替换后的最长重复字符

Leetcode 219. 存在重复元素 II
定长窗口滑动 维护窗口内是否有重复元素

Leetcode 424. 替换后的最长重复字符
maxCount维护历史最大数量，因为出内层while时都是（满足可替换）且right-left=maxCount+k，res每轮=max(res,right-left)，所以找到历史最大maxCount就可以找到最长长度

小巧思

n*n二维方阵原地旋转

先主对角线翻转，再水平翻转

螺旋矩阵

待补充

合并两个有序数组

从后往前扫填补就可以

将矩阵按对角线排序（未完成）

在同一个对角线上的元素，其横纵坐标之差是相同的。有了这个规律辅助，这道题就很容易做了，我直接用一个哈希表把每个对角线的元素存起来，想办法排序，最后放回二维矩阵上即可。

二维网格迁移

二维数组按一维数组往后走k步，后k个到前面。先把二维数组映射为一维的下标，然后处理一维（三次reverse）

带权随机选择算法

考虑把权重累加为一条长线段，随机数落在某个区间就选那个元素。用前缀和数组维护区间，二分查找随机数落在哪个区间。

1
2
3
4
5
6
7
8
9
// 不带权重
int randomIndex() {
    return rand() % n; // 返回一个 0 到 n-1 之间的随机整数
}

vector<int> w = {1, 3, 2}; // 权重数组

vector<int> prefixSum(w.size(), 0); // 前缀和数组

169. 多数元素

求众数：摩尔投票算法，维护一个候选元素和一个计数器，遍历数组，如果计数器为0，更新候选元素为当前元素；如果当前元素等于候选元素，计数器加1，否则减1。最后返回候选元素。
思想：两个不同的元素可以直接消掉，剩下的一定是众数

区间问题

排序区间起点，讨论end落在哪，落在外面则生成新区间

单调队列

239. 维护定长滑动窗口中的最值

是双端队列，维护一个严格单调递增或递减的队列，队头永远是当前窗口的最值

  • 入队：在队尾入队，且要对队尾进行修剪，因为新入队的元素“更年轻”，更有可能成为未来窗口的最值，所以更老且更没用的队尾要被修剪掉
    注意：不能弹出同等大小的老元素，因为后面pop时用值比较，若弹出同等大小，后面再pop时会把这个同等大小也pop出去

语法

1
2
3
4
5
6
auto cmp = [](pair<int,int> a,pair<int,int> b){return a.second<b.second;}; // 自定义比较器 的优先级
priority_queue<pair<int,int>,vector<pair<int,int>>,decltype(cmp)> pq(cmp); // true的优先级更低

//注意和sort区别
sort(v.begin(),v.end(),cmp); // cmp返回true说明a应该排在b前面

单调栈