双指针

Posted on | In ,

本文将针对双指针的使用场景进行讲解。

双指针作用

双指针指使用两个指针对数组进行操作，一般一个放首，一个放尾，或者两个都放在开头，移动速度或开始移动的时机不同。

常见的使用场景包括：

  • 两数求和（或者三数求和）：寻找两个数的和为一个特定的值
  • 数组就地交换
  • 正负数排序数组平方和处理（LeetCode977）
  • 删除符合条件的特定元素（字节跳动笔试题）

双指针难点总结

双指针在使用中往往会遇到如下问题：

  • 每个指针分别代表什么含义
  • 如何移动每个指针

本文将针对双指针中常见的一些应用场景下的含义及移动方法进行总结。

起始位置

  • 两个指针均从头开始移动
  • 一头一尾移动

移动方法

  • 如果符合条件，两个指针均向后移动，否则移动快指针
  • 快指针以慢指针k倍速移动

双指针指向数组两端，分别向中间收缩，用于解决两数求和的问题

注意事项

  • 使用前需要对数组排序
  • 循环判断条件为while(left < right)
  • 可能需要去除重复

1099. 小于 K 的两数之和

思路

和大于K，则右指针左移，否则左指针右移

18. 四数之和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
for(int i=0;i<nums.size()-3;i++){
    if(i > 0 && nums[i] == nums[i-1]) continue;
    for(int j=i+1;j<nums.size()-2;j++){
        if(j>i+1 && nums[j] == nums[j-1]) continue;
        int k = j+1, l = nums.size()-1;

        while(k < l){
            if(nums[i]+nums[j]+nums[k]+nums[l] < target)      k++;
            else if(nums[i]+nums[j]+nums[k]+nums[l] > target) l--;
            else{
                ans.push_back({nums[i],nums[j],nums[k],nums[l]});
                while(k < l && nums[k] == nums[k+1]) k++;
                while(k < l && nums[l] == nums[l-1]) l--;
                k++;
                l--;
            }
        }
    }
}

双指针延伸方法

滑动窗口法，用于搜索符合条件的连续子串

滑动窗口实际上就是一个队列，队列的长度根据符合条件的子串的长度，是不断发生变化的，通过遍历整个数组，就能找到符合条件的连续子串。我们一般使用双指针构成滑动窗口，将i,j分别指向窗口左右边界，通过移动i和j，即可将窗口进行滑动。

图片名称

LeetCode第3题 最长不含重复字符的子字符串

给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。

1
2
3
输入: "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
// 解法1
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        if(s.size() == 0) return 0;
        int max_str = 0;
        int left = 0;          //队列左侧
        unordered_set<int> lookup{};   //用无序set作为队列
        for(int i=0;i<s.size(); ++i){  //遍历s
            while(lookup.find(s[i]) != lookup.end()){   //右侧元素已经出现在字符串中
                lookup.erase(s[left]);         //弹出队列左侧元素，直到右侧元素不在当前字符串中
                left++;                        //窗口左侧右移
            }
            max_str = max(max_str, i-left+1);
            lookup.insert(s[i]);              //添加右侧元素
        }
        return max_str;
    }
};

// 解法2，使用一个map记录某个字符左侧的位置
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
       map<char, int> dic{};
       int i=-1, res = 0;
       for(int j=0;j<s.size(); j++){
           if(dic.find(s[j]) != dic.end()){
               i = max(i, dic[s[j]]);    // 找到两者中较大的作为左边界
           }
           dic[s[j]] = j;    //更新dic
           res = max(res, j-i);
       }
       return res;
    }
};

80. 删除有序数组中的重复项 II

给你一个有序数组 nums ，请你原地删除重复出现的元素，使每个元素 最多出现$k$次 ，返回删除后数组的新长度。

不要使用额外的数组空间，你必须在原地修改输入数组 并在使用 O(1) 额外空间的条件下完成。

这个题思路非常巧妙，我们分成两种情况讨论：

  • 对于前$k$个数字，我们可以直接保留
  • 而对于后面的数字，我们采用局部性原理处理，仅关注[len-k,len-1]这一段，如果当前数字(num)与当前写入位置前第k个元素不相同，那么可以保留，否则丢弃（num向后移动）
1
2
3
4
5
6
7
int removeDuplicates(vector<int>& nums, int k) {
    int len = 0;          // 指针1
    for(auto num : nums)  // 指针2
        if(len < k || nums[len-k] != num)  // 滑动窗口（大小为k）
            nums[len++] = num;   // 两个指针都递增
    return len;
}

双指针适用场景

子序列问题

392. 判断子序列

给定字符串 s 和 t ，判断 s 是否为 t 的子序列。

你可以认为 s 和 t 中仅包含英文小写字母。字符串 t 可能会很长（长度 ~= 500,000），而 s 是个短字符串（长度 <=100）。

字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，”ace”是”abcde”的一个子序列，而”aec”不是）。

1
2
3
4
5
6
7
8
9
10
11
12
13
//子序列实际上是在一个固定的解空间中按照一定顺序组成一个解，在此处应用到了两个指针，i和j，i指向解，j指向解空间，如果找到了解，那么两个指针都递增，否则只递增解空间的指针，代表后向搜索
bool isSubsequence(string s, string t) {
    int i = 0, j = 0;
    int m = s.size(), n = t.size();
    while(i < m && j < n){
        if(s[i] == t[j]){
            i++;    //找到某个解，解和解空间均递增
            j++;
        }
        else j++;   //继续搜索解空间
    }
    return i == m;
}

专题：字符串压缩

在有些情况下，需要我们对字符串进行压缩处理，如果能够实现原地修改算法，那么我们的字符串处理起来会很简单，本文将针对字符串压缩处理相关问题进行总结。

双指针例题

字节跳动2019春招笔试题——字符串处理

三个同样的字母连在一起是拼写错误，去掉一个：比如 helllo -> hello

两对一样的字母（AABB型）连在一起是拼写错误，去掉第二对的一个字母：比如 helloo -> hello

上面的规则优先“从左到右”匹配，即如果是AABBCC，虽然AABB和BBCC都是错误拼写，应该优先考虑修复AABB，结果为AABCC

输入例子1:
1
2
3
2
helloo
wooooooow
输出例子1:
1
2
hello
woow

解答

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<iostream>
using namespace std;
int main(){
    int n;
    cin >> n;
    string s{};
    while(n--){    //基本框架
        cin >> s;
        int j=0;    //第二个指针
        for(int i=0;i<s.size();++i){
            s[j++] = s[i];         //s[j] = s[i] //第二个指针总是超前第一个指针
            if(j>=3&&s[j-1]==s[j-2]&&s[j-2]==s[j-3]){
                j--;   //下一轮操作会覆盖当前位置元素
            }
            if(j>=4 && s[j-1] == s[j-2] && s[j-3] == s[j-4]){
                j--;
            }
        } 
        s.erase(s.begin()+j,s.end());   //字符串相当于进行了平移，没有用的东西都放在了j之后
        cout << s << endl;
    }
    return 0;
}

LeetCode 15 三数求和

给定一个包含 $n$ 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> ans{};
        if(nums.empty()) return ans;
        sort(nums.begin(),nums.end());
        int i=0;
        
        for(int i=0;i<nums.size();i++){
            int l = i+1;
            int r = nums.size() - 1;
            while(l<r){
                if(nums[i] + nums[l] + nums[r] == 0) {
                    ans.push_back(vector<int>{nums[i],nums[l],nums[r]});
                    while(l<r && nums[l] == nums[l+1] ) l++;   //去重处理
                    while(l<r && nums[r] == nums[r-1] ) r--;
                    l++;   //去重处理
                    r--;
                }
                else if(nums[i] + nums[l] + nums[r] < 0) l++;
                else r--;
            }
            while(i+1 < nums.size() && nums[i] == nums[i+1]) i++;  //去重处理
        }
        return ans;
    }
};

解法很简单，可以将三数求和转换为两数求和问题，即num[i] + num[j] = num[k]，做一些去重复处理即可

0%