4 - 双指针

准备春招，算法题冲冲冲！

如果某些数据具有单调性，可以尝试使用双指针算法来减少时间复杂度。

双指针

思路

针对问题先想一个暴力的方法（通常是 $O(N^2)$ ），如果循环量i和j之间有单调关系，则可以利用这种单调关系写一个双指针算法，以减少时间复杂度。

双指针算法的一般写法如下：

for (int i = 0, j = 0; i < n; ++i)
{
    while (j < i && check(i, j))
        j++;
    // 每道题目的具体逻辑...
}

时间复杂度为 $O(N)$ ，因为双指针的移动次数不会超过2n。

例题

799. 最长连续不重复子序列

这道题可以用双指针来做，用i维护连续不重复子序列的右端，用j维护连续不重复子序列的左端。输入a[i]后，让map[a[i]]计数增加，如果出现重复（map[a[i]] > 1），就让j右移，别忘了map[a[j]]计数减少。最后剩下的就是连续不重复子序列，长度为i - j + 1，记录它的最大值就是答案。

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

int main()
{
    int n;
    cin >> n;
    
    vector<int> a(100001);
    unordered_map<int, int> map;
    int lengthMax = -1;
    
    for (int i = 0, j = 0; i < n; ++i)
    {
        cin >> a.at(i);
        map[a.at(i)] += 1;
        
        // 看看是否重复了, 重复就右移j
        while (j <= i && map[a.at(i)] > 1)
        {
            map[a.at(j)] -= 1;
            ++j;
        }
        
        // 记录当前连续区间最长长度
        lengthMax = max(lengthMax, i - j + 1);
    }
    
    cout << lengthMax;
}

800. 数组元素的目标和

#include <iostream>
#include <vector>
using namespace std;

int main()
{
    int n, m, x;
    cin >> n >> m >> x;
    
    vector<int> a(100001), b(100001);
    for (int i = 0; i < n; ++i)
        cin >> a.at(i);
    for (int i = 0; i < m; ++i)
        cin >> b.at(i);
    
    // 一个从左开始, 一个从右开始
    for (int i = 0, j = m - 1; i < n; ++i)
    {
        // 如果大于给定和, 就让j往左走
        while (j >= 0 && a.at(i) + b.at(j) > x)
            --j;
        // 找到唯一解
        if (a.at(i) + b.at(j) == x)
        {
            cout << i << " " << j;
            break;
        }
    }
}

2816. 判断子序列

#include <iostream>
#include <vector>
using namespace std;

int main()
{
    int n, m;
    cin >> n >> m;
    
    vector<int> a(n), b(m);
    for (int i = 0; i < n; ++i)
        cin >> a.at(i);
    for (int i = 0; i < m; ++i)
        cin >> b.at(i);
    
    // i -> a[], j -> b[]
    for (int i = 0, j = 0; j < m; ++j)
    {
        if (a.at(i) == b.at(j))
        {
            ++i;
            // i == n说明a数组已被全部遍历完, a是b的子序列
            if (i == n)
            {
                cout << "Yes";
                return 0;
            }
        }
    }
    
    cout << "No";
}

53. 最大子数组和

可以用双指针来做，用i从头遍历到尾求和，如果和为负，就让j往前走，同时让和减去a[j]。

int maxSubArray(vector<int>& nums) {
    int maxSum = nums.at(0);
    int tmpSum = 0;
    for (int i = 0, j = 0; i < nums.size(); ++i)
    {
        tmpSum += nums.at(i);
        maxSum = max(maxSum, tmpSum);
        while (tmpSum < 0)
        {
            tmpSum -= nums.at(j++);
        }
    }
    return maxSum;
}

283. 移动零

用双指针来做，左边的指针永远指向0，右边的指针永远指向非0元素，然后进行交换即可。

void moveZeroes(vector<int>& nums) {
    int n = nums.size();
    for (int left = 0, right = 0; right < n; ++right)
    {
        while (left < right && nums.at(left) != 0)
        {
            ++left;
        }

        if (nums.at(left) == 0 && nums.at(right) != 0)
        {
            swap(nums.at(left), nums.at(right));
        }
    }
}

11. 盛最多水的容器

用双指针来做，左边的指针在0，右边的指针在height.size() - 1。注意到 当移动较短的板时，容器面积可能增大，我们只需一直移动较短的板，直到双指针相遇即可。

int getArea(vector<int>& height, int left, int right)
{
    return min(height.at(left), height.at(right)) * (right - left);
}

int maxArea(vector<int>& height) {
    int ans = 0;
    for (int left = 0, right = height.size() - 1; left < right;)
    {
        ans = max(ans, getArea(height, left, right));
        while(left < right)
        {
            if (height.at(left) < height.at(right))
                ans = max(ans, getArea(height, ++left, right));
            else
                ans = max(ans, getArea(height, left, --right));
        }
    }
    return ans;
}

167. 两数之和 II - 输入有序数组

使用双指针，一个在最左边，另一个在最右边，如果两数之和太小，让左指针右移；反之让右指针左移；最终返回答案。

参考代码如下：

vector<int> twoSum(vector<int>& numbers, int target) {
    int left = 0, right = numbers.size() - 1;
    while (left < right)
    {
        int sum = numbers[left] + numbers[right];
        if (sum == target)
            return {left + 1, right + 1};
        else if (sum < target)
            ++left;
        else 
            --right;
    }
    return {-1, -1};
}

15. 三数之和

遇事不决先排序，排完序后就能用双指针了。

我们让i从头到尾遍历一次，j指向i的下一个元素向右移动，k指向数组的最后一个元素向左移动，然后：

如果num[i] + num[j] + num[k] == 0，就将这三个数添加到答案中；
如果三数之和大于0，说明num[k]太大了，让它左移；
如果三数之和小于0，说明num[j]太小了，让它右移：

此外，答案中有重复元素，需要在添加答案后进行去重操作；此外，还有优化的地方，如果nums[i]已经大于0了，那三数之和怎么加都大于0，就没必要继续了。正确的代码如下：

vector<vector<int>> threeSum(vector<int>& nums)
{
    vector<vector<int>> ans;

    sort(nums.begin(), nums.end());
    for (int i = 0, j = 1, k = nums.size() - 1; i < nums.size() - 1; ++i)
    {
        j = i + 1, k = nums.size() - 1;
        // 如果num[i] > 0, 它后面的元素也必大于0
        if (nums.at(i) > 0)    
            break;
        // 跳过重复元素
        if (i >= 1 && nums.at(i) == nums.at(i - 1))
            continue;
        // 找j和k
        while (j < k)
        {  
            int sum = nums.at(i) + nums.at(j) + nums.at(k);
            if (sum > 0)    --k;
            else if (sum < 0)  ++j;
            else
            {   
                ans.push_back({nums.at(i), nums.at(j), nums.at(k)});
                --k, ++j;
                // 跳过重复元素
                while (j < k && nums.at(j) == nums.at(j - 1))
                    ++j;
                while (j < k && nums.at(k) == nums.at(k + 1))
                    --k;
            }
        }
    }
    return ans;
}

42. 接雨水

利用双指针和两个变量（记录左/右侧最高点）即可“竖着接雨水”：

从两头开始遍历，分别记录左边和右边的最大高度
如果现在左边的高度比右边的低，说明左边的最大高度也比右边的低；左边可以进行接水；
反之，右边可以进行接水。
接完水后不要忘了顺便让双指针位移。

int trap(vector<int>& height) {
    int ans = 0;
    int lMax = 0, rMax = 0;
    int left = 0, right = height.size() - 1;
    while (left < right)
    {
        lMax = max(lMax, height.at(left));
        rMax = max(rMax, height.at(right));

        if (left < right && height.at(left) < height.at(right))
            ans += lMax - height.at(left++);
        if (left < right && height.at(left) >= height.at(right))
            ans += rMax - height.at(right--);         
    }
    return ans;
}

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

这道题使用双指针，左边的指针遍历到重复数字就停止，右边的则找到下一个不重复的，与左边交换。

代码如下：

int removeDuplicates(vector<int>& nums) {
    int left = 0;
    for (int right = 0; right < nums.size(); ++right)
    {
        if (nums[left] != nums[right])
        {
            ++left;
            nums[left] = nums[right];
        }
    }

    return left + 1;
}

和这道题类似的：

5. 最长回文子串

首先，先写一个找回文串的算法：使用双指针，从中心向两端扩散。而对于中心位置的确定分两种情况，如果回文串长度为奇数，那么中心位置就有一个；如果是偶数，中心位置就有两个。因此找回文串的算法可以这样写：

string getPalindrome(const string& s, int left, int right)
{
    while (left >= 0 && right < s.size() && s[left] == s[right])
    {
        left--;
        right++;
    }

    return s.substr(left + 1, right - left - 1);
}

接下来看看如何找最长回文子串，我们只需遍历字符串所有位置，分回文串长度为奇偶两次情况获取回文子串，然后取最长即可：

string longestPalindrome(string s) {
    string ans = "";
    for (int i = 0; i < s.size(); ++i)
    {
        string s1 = getPalindrome(s, i, i);
        string s2 = getPalindrome(s, i, i + 1);
        ans = ans.size() < s1.size() ? s1 : ans;
        ans = ans.size() < s2.size() ? s2 : ans;
    }
    return ans;
}

参考资料

算法基础课 - AcWing

双指针​

思路​

例题​

参考资料​

双指针

思路

例题

参考资料