数组双指针技巧

1快慢指针

1.1有序数组去重

  • 思路：

    如果毎找到一个重复元素就立即原地删除它，由于数组中删除元素涉及数据搬移，整个时间复杂度是会达到 O(N^2)

    快指针探路，找到不重复的元素再赋值给慢指针

  • 伪代码：

1
2
3
4
5
6
7
while fast<size{
    if num[fast] != num[slow]{
        slow++;
        num[slow] = num[fast];
    }
    fast++;
}

1.2数组元素原地删除

  • 思路：如果fast遇到值为val的元素，则直接跳过，否则就赋值给 slow指针，并让slow前进一步。

  • 伪代码：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    val=2
    [0,1,2,2,4]→[0,1,4]
    while fast<size{
        if num[fast]!=val{
            num[slow]=num[fast];
            slow++;
        }
        fast++;
    }

1.3滑动窗口框架

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/* 滑动窗口算法框架 */
void slidingWindow(string s, string t) {
    unordered_map<char, int> window;

    int left = 0, right = 0;
    while (right < s.size()) {
        char c = s[right];
        // 右移（增大）窗口
        right++;
        // 进行窗口内数据的一系列更新

        while (window needs shrink) {
            char d = s[left];
            // 左移（缩小）窗口
            left++;
            // 进行窗口内数据的一系列更新
        }
    }
}

2左右指针

2.1二分查找

  • 思路

    • 因为我们初始化 right = nums.length - 1

    • 所以决定了我们的「搜索区间」是 [left, right]

    • 所以决定了 while (left <= right)

    • 同时也决定了 left = mid+1 和 right = mid-1

    • 因为我们只需找到一个 target 的索引即可

    • 所以当 nums[mid] == target 时可以立即返回

  • 伪代码
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    int left = 0, right = nums.size() - 1;
    while(left <= right) {
        int mid = (right + left) / 2;
        if(nums[mid] == target)
            ... 
        else if (nums[mid] < target)
            left = mid + 1; 
        else if (nums[mid] > target)
            right = mid - 1;
    }

2.2两数之和

  • 思路：类似二分查找

2.3反转数组

  • 思路：左右指针，交换数值

2.4回文串判断

2.5最长回文串

  • 思路：中心向两端扩散，奇数偶数各来一遍
  • 伪代码：
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    for(遍历字符串)
        //奇数情况
        left=i，right=i；
        while(左边界&&右边界&&s[left]=s[right]){
            left--;
            right++；
        }
        更新res，res.length与right-left-1作比较，取substr
        //偶数情况
        left=i，right=i+1；
        ...剩下同上