算法总结：双指针算法（什么时候该使用、如何使用）_双指针的使用条件

简介

双指针算法指的是在重复遍历对象的过程中，不是在两个循环中使用单个指针进行重复访问，而是在一个循环中使用两个相同方向（快慢指针）或者相反方向（对撞指针）的指针进行访问。

一：从一个C++语言程序开始

给你 n 个非负整数 a1，a2，…，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0) 。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

示例：

输入：[1,8,6,2,5,4,8,3,7]
输出：49
解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。

注意：
n = height.length
2 <= n <= 3 * 104
0 <= height[i] <= 3 * 104

1.基础解法

笔者拿到题的第一反应，就这？
这也叫中等题？题目描述的这么高大上，架不住我上手就是一个二重循环的暴力算法啊，分分钟秒掉收刀好吧，于是动手写了如下代码：

题解：

class Solution {
public:
    int maxArea(vector<int>& height) {
        int maxarea=0;
        //遍历数组，对每一组都计算容积，大的话进行更新
        for(int i=0;i<height.size();i++)
            for(int j=i+1;j<height.size();j++){
                int tmparea=min(height[i],height[j])*(j-i);
                maxarea=max(tmparea,maxarea);
            }
    return maxarea;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13

写完运行示例，通过，换一个再运行，再通过。ok，笔者心想过了，自信的提交代码，等待结果…
”超出时间限制“
啊咧？
emm…看来没这么简单啊，显然n^2的时间复杂度是不能过的，那小修小改估计也没用，只能换算法

2.双指针解法

显然，我们需要在一个循环中把这题搞定。

我们设置两个指针分别指向数组的左右两端，这两个指针和底边围成的容器就是初始容器，我们记录下此时的容器大小。
进入循环，每次一次移动一个指针。那么移动的条件呢？从需求出发，我们需要让容器最大，而每次不论是移动哪一个指针，容器的底边都会变小一个单位，显然移动对应数字较小的那个指针保留较大的指针更容易达到需求。

双指针算法题解：

class Solution {
public:
    int maxArea(vector<int>& height) {
        //定义两个指针分别指向头和尾
        int head=0,tail=height.size()-1;
        //计算以头尾为底边的初始容器的面积
        int maxarea=min(height[head],height[tail])*(tail-head);

        while(tail>head){
            //比较两个指针的边的长度，保留高的一个更容易得到大的面积
            if(height[head]>height[tail]) tail-=1;
            else head+=1;
            int tmparea=min(height[head],height[tail])*(tail-head);
            maxarea=max(tmparea,maxarea);
        }
        return maxarea;

    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

复杂度分析
时间复杂度：O(N)，双指针总计最多遍历整个数组一次。
空间复杂度：O(1)，只需要额外的常数级别的空间。

二：Leetcode实战

Leetcode第十五题-三数之和
题目描述：
给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。

示例 1：
输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]

示例 2：
输入：nums = [0，0，0，0]
输出：[[0，0，0]]

提示：
0 <= nums.length <= 3000
-105 <= nums[i] <= 105

双指针算法题解：

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int> > ans;
        //对数组进行排序
        sort(nums.begin(),nums.end());
        
        for(int i=0;i<nums.size();i++){
        	//避免出现重复解
            if(i>0 && nums[i]==nums[i-1]) continue;
            
            //定义双指针
            int head=i+1,tail=nums.size()-1;
            while(head<tail){
            	//避免出现重复解，如[0，0，0，0]
                if(head>i+1 && nums[head]==nums[head-1]){
                    head++;
                    continue;
                } 
                int sum=nums[head]+nums[tail]+nums[i];
                
                //双指针核心代码
                if(sum<0)
                    head++;
                if(sum>0)
                    tail--;
                if(sum==0){
                    ans.push_back({nums[i],nums[head],nums[tail]});
                    //这里head++或是tail--都可以，为了让循环继续下去
                    head++;
                }
            }
        }
        return ans;
    }
};
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

看出区别在哪了吗：

//这是双指针的写法
while(head<tail){
    if(sum<0)
        head++;
    if(sum>0)
        tail--;
    if(sum==0)
        //...
}
//这是普通写法
for(int i=0;i<m;i++)
    for(int j=0;j<n;j++){
        if(sum==0)
            //...
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

总结

双指针将一个两层循环转化成了一层循环，时间复杂度也从n^2变成了n，那么什么时候会需要使用双指针呢？
一般来讲，当遇到需要对一个数组进行重复遍历时，可以想到使用双指针法
如何实现将普通写法到双指针写法的转换呢？
说是指针，其实是设置两个int变量分别赋值为数组的首和尾，在一层循环内，每次只对其中一个指针进行移动，找到判断指针移动的条件是双指针的核心，在该题中，是一个求和为0的问题，那么当sum>0时，显然说明整体的值太大了，应该让其更小，故对于排序后的数组将尾指针左移，显然，sum和0的大小便是此题中判断指针移动的条件

♥觉得有用，给个赞吧♥

注

题目来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/string-to-integer-atoi
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

博客著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。