数组双指针——左右指针

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

n数之和

有序数组的平方

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

回文串相关

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

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

二分查找

数组有序就考虑

找一个元素

左闭右开区间[left, right)

  • while(left < right) 因为当left == right时，区间已经没有元素了，可以跳出
  • left = mid + 1; left所指的元素还要再找，所以指向跳过mid这个元素的位置
  • right = mid; right所指向的mid刚好不用再找
1
2
3
4
5
6
7
8
9
10
int binarySearch(vector<int>& nums, int target){
  int left = 0, right = nums.size();
  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
}

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
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++;
}

滑动窗口（重点）

同样用左闭右开区间。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. 伸：此时窗口一定合法，更新最大值
        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++;
        }
    }

通用外层框架

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++;
    }
}
  1. 最小覆盖子串
    维护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中

小巧思

n*n二维方阵原地旋转

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

螺旋矩阵

待补充

合并两个有序数组

从后往前扫填补就可以

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

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

二维网格迁移

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