浅谈双指针算法_双指针必须先排序

目录

算法概述

案例分析

1、删除有序数组中的重复项

2、环形链表

3、盛最多水的容器

4、有效三角形的个数

5、三数之和

6、复写零

内容总结

---

算法概述

双指针指的是在遍历元素的过程中，不是使用单个指针进行访问，而是使用两个指针进行访问，从而达到相应的目的。一些特殊的情况利用双指针可以将原本时间复杂度为O(N²)的操作简化为O(N)级别的。而且，人们根据大量的做题经验归纳出了几种特殊的双指针算法，例如「对撞指针」、「快慢指针」、「分离双指针」等。其中，对撞指针就是指的两个指针从范围的两端相向而行，快慢指针就是指两个指针的移动速度或是每次移动的范围有快慢之分，分离双指针就是指的两个指针分别在两个不同的数组或是容器中。

当然，干巴巴的说概念没多大意义，接下来就让我们通过具体的例题来感受这个双指针算法。

案例分析

1、删除有序数组中的重复项

题目描述

26. 删除有序数组中的重复项https://leetcode.cn/problems/remove-duplicates-from-sorted-array/思路分析

这题是一个很常规的双指针题目，用到的就是快慢指针，下面是具体的思路分析：

首先注意数组是有序的，那么重复的元素一定会相邻。要求删除重复元素，实际上就是将不重复的元素移到数组的左侧。所以我们考虑用 2 个指针，用来维护两个范围，一个是当前的有效范围，即没有重复元素的范围，另一个是当前已经处理过的范围。假设我们用eff维护有效范围，cur用于维护当前范围，即 [0, eff] 区间内的是有效范围，cur指针用于枚举数组。

那么我们就可以判断cur位置的数是否等于cur-1，如果等于，就说明是重复元素，直接忽略（不能加入有效范围），如果不等于，那么就将 cur 位置的数和 eff+1 位置的数交换，然后令eff自增1。这样当cur走到最后时，eff所在的位置，就是有效数组的区间范围。

如下是我的题解，仅供参考：

class Solution {
public:
    int removeDuplicates(vector<int>& nums) 
    {
        int eff = 1, cur = 0;
        while(++cur < nums.size())
        {
            if(nums[cur] != nums[cur - 1])
            {
                nums[eff++] = nums[cur];
            }
        }
        return eff;
    }
};

2、环形链表

题目描述

141. 环形链表https://leetcode.cn/problems/linked-list-cycle/思路分析

这是一个很经典的链表题目，如下是具体的思路分析：

这题就是属于那种知道就会，不知道就不会的那种。因为大多数人第一次接触这题很难有思路，但一旦知道怎么做之后很快就记住了。

好了我们不多废话，直接看解法：先定义一对快慢指针fast和slow，它们分别都从头开始，fast每次向后走两步，slow每次向后走一步。如果出现fast==slow的情况，那么就是有环。否则如果fast如果走到了NULL，那就说明没环。

至于证明，感兴趣的可以到下面这篇博客中找，有对应一样的题目，附带证明。

链表题目强化练_小白菜※的博客-CSDN博客

如下是我的题解，仅供参考：

bool hasCycle(struct ListNode *head) 
{
    if(head == NULL)
        return false;
    struct ListNode *fast = head, *slow = head;
    while(fast && fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;
        if(slow == fast)
            return true;
    }
    return false;
}

3、盛最多水的容器

题目描述

11. 盛最多水的容器https://leetcode.cn/problems/container-with-most-water/思路分析

这是一道很经典的面试题，但大多数人看到这题时很难想到用双指针的解法：

在解决这道题之前，我们先要归纳出容纳的水的面积公式为：width*high。而这个width就是指的两个“柱子”之间的距离，而high就是指的两个“柱子”之中的较短者。

所以，我们可以控制让其中一个因素具有单调性，这样另一个因素就可以根据这个单调性来“对症下药”了。具体的做法是：让左右两个指针先在数组的左右两端，这样就保证了width的最大，这样不管下一个指针怎么移动，width都是在单调递减的，所以要想保证获取的下一个面积有相对较大的可能，我们就要舍弃掉左右指针中较小的那一个。这期间还需要有一个变量用于保存结果并不断与当前面积比较大小并获取最大。

如下是我的题解，仅供参考：

class Solution {
public:
    int maxArea(vector<int>& height) 
    {
        int left = 0;
        int right = height.size() - 1;
        int max_area = 0;
        while(left < right)
        {
            // 走一趟，求出最大
            int high = std::min(height[left], height[right]);
            int cur_area = (right - left) * high;
            max_area = std::max(max_area, cur_area);
            // 谁小让谁走，一样小的，无所谓
            if(high == height[left])
                left++;
            else 
                right--;
        }
        return max_area;
    }
};

4、有效三角形的个数

题目描述

611. 有效三角形的个数https://leetcode.cn/problems/valid-triangle-number/思路分析

首先我们需要知道形成三角形的条件：当两条较小边之和大于另一条边时，就一定可以形成三角形。所以我们可以先对数组排序，然后想办法利用这个有序的条件进行操作。

而数组有序之后，由于有三条边需要控制，我们很难一下子控制三个变量，所以我们可以先固定一个变量，比如要当作最大或最小的那条边，我们这里以最大的为例，那么固定值就从后往前（从大到小）进行枚举。我们就对固定值左边的范围去寻找对应的符合范围的两条边，那么这样就好处理了：采用对撞数组的方式，让两个指针相向而行，如果和大于固定值，就说明可以组成三角形，那么就将个数加上左右指针之间的差值（因为此时这个范围内的数与右指针相加是一定大于固定值的），随后让右指针左移一个并继续。如果和小于固定值，就需要让左指针右移一个，然后继续判断了。

如下是我的题解，仅供参考：

class Solution 
{
public:
    // 思路：先排序，然后根据有序数组利用双指针来做
    int triangleNumber(vector<int>& nums) 
    {
        // 排序，时间复杂度 O(logN)
        std::sort(nums.begin(), nums.end(), std::less()); 
        // 双指针：先固定一个，然后i、j指针在剩余区域相向而行
        int count = 0;
        for(int k = nums.size() - 1; k > 1; k--)
        {
            int i = 0, j = k - 1;
            while(i < j)
            {
                if(nums[i] + nums[j] > nums[k])
                {
                    count += j - i;
                    j--;
                }
                else
                {
                    i++;
                }
            }
        }
 
        return count;
    }
};

5、三数之和

题目描述

15. 三数之和https://leetcode.cn/problems/3sum/思路分析

这题其实如果没有要求不包含重复项这一条件还并不是很难，但就是因为这个要求使得很多人（包括我）卡了很久。

如果不考虑“不包含重复项”这一条件，那么大致的思路就可以是：先对数组排序，然后从后往前枚举k，接着对k左边的区域采取对撞指针的方式，就可以找出所有符合条件的三元组。这时我们再来额外的考虑这个“不包含重复项”的条件。由于数组是已经排序好的，所以相同的数据一定是相邻的，那么此时我们只需要对i、j、k每一个单独使其不处理相同数据的情况不就行了吗？这里的思路就和第一个案例很像了，遇到 nums[cur] == nums[cur-1] 的情况就直接跳过不处理即可。

如下是我的题解，仅供参考：

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) 
    {
        // nums[i] + nums[j] + nums[k] = 0 
        // 先排序，然后固定一个（k），通过双指针来确定剩下的两个{i、j}
        // 由于数组是有序的，所以去重操作只需要忽略当前项等于前一个的情况即可
        sort(nums.begin(), nums.end());       
        vector<vector<int>> ans;
        int k = nums.size() - 1;
        while(k > 1)
        {
            int i = 0, j = k - 1;
            while(i < j)
            { 
                if(nums[i] + nums[j] + nums[k] > 0) j--;
                else  if(nums[i] + nums[j] + nums[k] < 0) i++;
                else
                {
                    //添加完之后i和j继续移动，防止死循环
                    ans.push_back({nums[i], nums[j], nums[k]});            
                    int ipast = nums[i];
                    int jpast = nums[j];
                    while(i < j && nums[i] == ipast) i++;   
                    while(i < j && nums[j] == jpast) j--;                    
                }
            }            
            int past = nums[k];
            while(k > 1 && nums[k] == past) k--;     
        } 
        
        return ans;
    } 
}; 

6、复写零

题目描述

1089. 复写零https://leetcode.cn/problems/duplicate-zeros/思路分析

这题其实很容易想到的就是借助一个额外的数组，然后在另一个数组中进行操作，这样就可以很容易的得出答案。但是，由于题目要求我们必须就地操作，所以我们不能用这种方法。不过我们可以根据这种方法，来推导模拟出就地操作的方法。

大致思路就是：设置两个指针，先让它们模拟一次在两个数组中操作的情况下，结束时这两个指针的位置，然后根据位置从后往前推就可以了。只不过有一种特殊情况，就是模拟异地的那个指针可能会出现越界的情况，这是因为有一种最后多出一个0的情况，但由于这种情况非常的特殊，所以我们只需要对这一种情况特殊处理就可以了。

如下是我的题解，仅供参考：

class Solution {
public:
    void duplicateZeros(vector<int>& arr) 
    {
        // 思路：面向结果编程。通过异地数组的方式推导就地数组的规律
        int cur = 0, eff = 0;
        while(eff < arr.size())
        {
            if(arr[cur] == 0)
            {
                eff++;
            }
            cur++;
            eff++;                
        }
 
        if(--cur != --eff)
        {
            // 特殊情况/细节处理：模拟的出现越界的情况，那么一定是0的问题
            if(eff == arr.size())
            {
                arr[--eff] = arr[cur];
                eff--;
                cur--;
            }
 
            while(cur >= 0)
            {
                if(arr[cur] == 0)
                {
                    arr[eff--] = 0;
                }
                
                arr[eff--] = arr[cur--];
            }
        }
 
    }
};

内容总结

在数组有序的情况下就要首先考虑二分和双指针，而对于数组有一定单调性或者某一因素具有一定单调性的时候，也是可以考虑使用双指针的。上面的几个案例只是为了帮助我们更好的理解、感受这种思路，并没有囊括所有的双指针题型。

其实双指针并不是一种算法，更倾向于是一种思路。有时双指针并不一定是解题的关键，有些时候只是解题的某一小部分，比如快速排序。所以我们不要拘泥于双指针算法或者双指针题型，这只是一种思想，或者处理数据的一种方式，并不是一种模板或者套路。