数组双指针——左右指针

两端向中间

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
}

数组双指针——快慢指针

去重/删除/移动元素

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

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)全遍历的部分情况不用扫
问三个问题：

  1. 窗口什么时候右移？（fast++）
  2. 窗口什么时候左移？（slow++）
  3. 什么时候更新结果？
    外循环更新right，内循环更新left
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 滑动窗口算法框架伪码
int left = 0, right = 0;

while (right < nums.size()) {
    // 右移增大窗口
    window.addLast(nums[right]);
    right++;
    
    while (window needs shrink) { // 已经找到符合条件的答案，需要缩小
        // 更新结果
        update result
        
        // 缩小窗口
        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二维方阵原地旋转

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

螺旋矩阵

待补充