TwoPointer

2020-02-02 09:37 CST

2020-02-02 09:37 CST

双指针

双指针是这样的模式:两个指针朝着左右方向移动(双指针分为同向双指针和异向双指针),直到他们有一个或是两个都满足某种条件。双指针通常用在排好序的数组或是链表中寻找对子。比如,你需要去比较数组中每个元素和其他元素的关系时,你就需要用到双指针了。

我们需要双指针的原因是:如果你只用一个指针的话,你得来回跑才能在数组中找到你需要的答案。这一个指针来来回回的过程就很耗时和浪费空间了 — 这是考虑算法的复杂度分析的时候的重要概念。虽然brute force一个指针的解法可能会奏效,但时间复杂度一般会是O(n²)。在很多情况下,双指针能帮助我们找到空间或是时间复杂度更低的解。

左右指针

有些情形下,不应该用左右指针,比如我们在单链表上不能往回移动的时候

识别使用双指针的招数:

  • 一般来说,数组或是链表是排好序的,你得在里头找一些组合满足某种限制条件
  • 这种组合可能是一对数,三个数,或是一个子数组

举例

11 Container With Most Water

题意:给定数组,在数组对应的图中求面积最大值($S = (j-i)*min(a[i],a[j])$)

解法: 使用双指针,从两个边界开始,每次都让更短的那条边向内移动。

class Solution {
public:
    int maxArea(vector<int>& height) {
        int left=0,right = height.size()-1;
        int area = 0;
        while(left!=right){
            int areatmp = (right-left)*min(height[left],height[right]);
            if (areatmp>area){
                area=areatmp;
            }
            if(height[left]<height[right]){
                left++;
            }else {
                right--;
            }
        }
        return area;
    }
};

方法正确性说明:

通俗的讲就是因为我们缩短了矩形在x轴上的边长,必须增大y轴上的边长,这只能通过移动最短边得到可能更大值。

严格一点:我们用(i,j)表示left的index为i,right为j。 我们可以知道:在(i,j)时,i,j中必有一个是经历过的H中最大的(否则按照算法在该点将停止不动)。 我们只需要证明,我们移动后,被消去的可能状态要么被计算过,要么小于我们已经被计算过的某个状态即可。简单讨论下就可以得证了

15 3-Sum

题意:给定数组,返回所有使得三数之和为0的三元组(不能出现重复的三元组)

题解:排序后使用双指针

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> ans;
        int n = nums.size();
        if(n<3){
            return ans;
        }
        sort(nums.begin(),nums.end());
        for(int i=0;i<n;i++){
            if(i>0 && nums[i]==nums[i-1]){
                continue;
            }
            int left = i+1, right = n-1;
            while(left<right){
                if(nums[i]+nums[left]+nums[right]>0){
                    right--;
                } else if(nums[i]+nums[left]+nums[right]<0){
                    left++;
                } else {
                    vector<int> anstmp ({nums[i],nums[left],nums[right]});
                    ans.push\_back(anstmp);    
                    while(left<n-1 && nums[left]==nums[left+1]) left++;
                    while(right>0 && nums[right]==nums[right-1] ) right--;
                    left++;
                    right--;
                }
            }
        }
        return ans;
    }
};  

167 Two Sum II - Input array is sorted

977 Squares of a Sorted Array

  • 输出一个排好序的数组的平方数组(简单)
  • 比较两个字符是否相等,字符中包括得有退格键(中等)

快慢指针

这种方式下,两个指针的在数组上(或是链表上,序列上)的移动速度不一样,可以利用线性同余方程证明他们肯定会相遇(类似于跑道上面跑得快的人套圈跑得慢的人)。这种方法在解决有环的链表和数组时特别有用

一般需要用快慢指针模式的问题:

  • 问题需要处理环上的问题,比如环形链表和环形数组
  • 当你需要知道链表的长度或是某个特别位置的信息的时候

举例

  • 链表是否有环(简单)
  • 链表是否满足回文(中等)
  • 环状数组中检测环(困难)