leetcode - 双指针题目

文章目次

前言
题1 移动零：
思绪：
参考代码：
题2 复写零：
思索：
参考代码：
题3 快乐数：
思索：
参考代码：
题4 盛最多水的容器：
思索：
参考代码：
题5 有效三角形的个数：
思索：
参考代码：
题6 查找总代价为目标值的两个商品：
思索：
参考代码：
题7 三数之和：
思索：
参考代码：
题8 四数之和：
总结

---

前言

路漫漫其修远兮，吾将上下而求索；

---

题1 移动零：

283. 移动零 - 力扣（LeetCode）

提取题干意思：

思绪：

数组分别类题型（数组分块）：给了我们一个数组，而且订定了一个规则，让我们在这个规则下将该数值分别为多少个区间
本题：

使用双指针，指针cur 从左往右遍历扫描数组，指针dest指向已处置惩罚地区非零元素末了一个位置，图解如下：

相当于指针cur、dest 将数据分别为了三段：[0,dest] 为非0的数据地区、[dest+1 , cur-1] 为0的数据地区，[cur,n-1] 为待扫描的数据地区（其中n表现数据个数）；
流程：eg. nums = [0,1,0,3,12]

思绪总结：

注：双指针思想是快排中最核心的思想；虽可以办理快排题目，但是当数据量特殊大的时间（例如相同的数据很多时），该方法的时间复杂度就靠近N^2，因此快排不能办理比力恶心的数据（重复的数据多）；
参考代码：

1.     void moveZeroes(vector<int>& nums)
2.     {
3.         int n = nums.size();
4.         int cur = 0, dest = -1;
5.         while(cur<n)
6.         {
7.             if(nums[cur])
8.             {
9.                 ++dest;
10.                 swap(nums[dest] , nums[cur]);
11.             }
12.             cur++;
13.         }
14.     }

复制代码

优化 - cur 的遍历可以使用范围for，代码如下：

1.     void moveZeroes(vector<int>& nums)
2.     {
3.         int cur = 0;
4.         for(auto& e:nums)
5.         {
6.             if(e)
7.             {
8.                 swap(e , nums[cur]);
9.                 cur++;
10.             }
11.         }
12.     }

复制代码

题2 复写零：

​​​​​​1089. 复写零 - 力扣（LeetCode）

提取题干意思：

思索：

我们先思索一下，异地操纵（借助于其他空间）怎样实现：

需要一个指针cur在旧数组上遍历，一个指针dest在新数组上遍历，当cur 遇到了0 就让dest 写两个0，cur 遇到非0，就让dest 写这个数据；图解如下：

Q1：是否可以从左往右直接使用双指针？

• 本题不可，由于遇见0要在原数组上写两个0，会覆盖掉后面的数据；但是假如是删除值为val 的题，就可以这么做；
  

Q2：既然从左往右不可行，那么从右往左是否可行呢？
从右往左的话，就需要找到cur 末了一个所要“复写”的位置，怎样找？

• 这与整个数组中0的个数有关系，可以先使用双指针（cur,dest）从左往右遍历（cur遇到0,dest走两步，非0dest走一步;当cur 走到末了一个数据或者dest 走到末了一个的时间，cur 指向的位置就是末了一个所要“复写”的位置），找到末了一个所要复写的位置，然后此时cur 、dest 的位置就是从右往左复写数据时的位置，思绪图如下：
  

注：dest 指向有效数据的末了，初始化为-1；cur 初始化为0；

但是，假如当cur 指向0，而dest 以后走两步大概就会越界，假如dest 越界了；而此时cur 、dest 的位置会作为从右往左复写数据时的位置，但是dest 已经越界了，故而这是有题目标；
办理方法：在找位置竣事后判定dest 是否合法（dest小于便是n-1就是合法的范围 ，但是dest 假如越界是肯定便是n）;假如合法什么都不做，假如不合法，dest = n-1 ，cur--;arr[n-1] = 0，如下图：

即，在找末了一个所要复写的位置的时间，有三种环境回导致循环竣事：

参考代码：

1.     void duplicateZeros(vector<int>& arr)
2.     {
3.         int n = arr.size();
4.         int cur = 0, dest = -1;
5.         //先从左往右遍历，找到cur 指向的最后一个数据
6.         while(cur<n)
7.         {
8.             if(arr[cur]==0) dest+=2;
9.             else ++dest;
10.             //在此过程中dest 可能会越界
11.             //在cur 自增前判断dest 是否越界
12.             if(dest >= n-1) break;//因为n-1 是最后一个有效位置
13.              cur++;
14.         }
15.         //边界情况处理，dest 越界了一定是为n
16.         if(dest==n)
17.         {
18.             arr[n-1] = 0;
19.             dest-=2;
20.             --cur;
21.         }
22.         //从先有的cur dest 的位置进行复写操作
23.         while(cur>=0)
24.         {
25.             if(arr[cur]==0)
26.             {
27.                 arr[dest--] = 0;
28.                 arr[dest--] = 0;
29.             }
30.             else
31.             {
32.                 arr[dest--] = arr[cur];
33.             }
34.             cur--;
35.         }
36.     }

复制代码

题3 快乐数：

202. 快乐数 - 力扣（LeetCode）

提取题干意思：

思索：

根据例子，画图思索：eg. 19 、2

对于19，末了得到是1在循环，故而返回的是true;对于2，末了得到的不是1的循环，以是返回false;
要么末了是1，陷入1的循环；要么不是1但是末了陷入一个循环之中
图解是否感觉有点熟悉？是不是有一点像链表，假如转换成链表，就是判定这链表环中的值即可（由于一旦有1，就肯定是1为一个单独的循环);而在链表 - 判定链表是否有环，是用快慢双指针来办理；
可以将本题抽象成链表，一个数变革成一个数可以抽象成这些数串联了起来；而且在本题中不消判定是否有环，只需要判定环中的值便可；

需要注意的是，slow 初始化为第一个数据的位置，fast 初始化为slow 的下一个位置；
只需要判定这两个值相遇的值是不是1即可，是1就返回true ,不是1则返回false;

在这个过程中是肯定成环的；
   注：
  1、在带环的链表中，快慢双指针肯定会相遇，而且肯定会在环中相遇；
  2、本题中固然不像链表中是一个一个结点，只是一个一个的数 ， 我们也可以让数来充当“指针”；不要被指针这个词限定了头脑，此地方讲的指针并不是真正的指针，而是在数组中使用双指针的时间可以用数组下标来充当指针，因此“双指针”只是一种思想；
  本题题干中：

，以是就肯定回成环，但是假如题干假如没有给这个提示呢？
那么分析地时间，就会分析出第三种环境：变下去不会成环；存在不成环的环境吗？假如题干没有这个提示，我们又该怎样办理？
证明：为什么在变革的过程中肯定会有环？
我们先来相识一个原理：鸽巢原理（抽屉原理）
注：我们的证明会用到鸽巢原理

取 9999999999 是由于它是 2.1*10^9 同样位数中的最大的数，可以靠它看一下范围；
对于 9999999999 来说，颠末“操纵”它每一位的和为 9^2*10 = 810，也就是9999999999颠末“操纵”之后所能酿成的最大的数，即对于 9999999999 来说有810 个巢，而 2.1*10^9 小于9999999999，那么  2.1*10^9 颠末操纵之后的效果肯定小于便是9999999999 颠末“操纵”之后的效果810，即2.1*10^9 的巢得个数肯定小于便是810而且大于便是1；
2.1*10^9 的巢得个数：[1，810]
那么一个数假如进行了“操纵”大于810 次（操纵次数是无穷的），肯定就会循环，即该数肯定成环；（即将大于810 的鸽子放到810 个巢里面，肯定有一个巢中的鸽子数量大于1）就可以证明没有第三种环境：变下去不会成环；
颠末上述证明，数据在变革的过程中肯定会成环；
参考代码：

1.     //获取一个数的每一个位置上的平方和
2.     int getbit(int n)
3.     {
4.         int tmp = n, sum  = 0;
5.         while(tmp)
6.         {
7.             int t  = tmp%10;//每一位
8.             sum += t*t;//平方和
9.             tmp/=10;//迭代
10.         }
11.         return sum;
12.     }
13.     bool isHappy(int n)
14.     {
15.         //通过鸽巢原理可以证明一定成环，所以可以利用快慢双指针来解决这个问题
16.         //注意slow 与 fast 的初始化！
17.         int slow = n , fast = getbit(n);
18.         //当slow 与 fast 相遇的时候，一定在环中相遇，此时只需要判断相遇的值便可
19.         while(slow!=fast)
20.         {
21.             //slow 一次走一步
22.             //fast 一次走两部
23.             slow = getbit(slow);
24.             fast = getbit(fast);
25.             fast = getbit(fast);
26.         }
27.         if(slow == 1) return true;
28.         else return false;
29.     }

复制代码

可以优化一下上面的参考代码，优化代码如下：

1.     //获取一个数的每一个位置上的平方和
2.     int getbit(int n)
3.     {
4.         int tmp = n, sum  = 0;
5.         while(tmp)
6.         {
7.             int t  = tmp%10;//每一位
8.             sum += t*t;//平方和
9.             tmp/=10;//迭代
10.         }
11.         return sum;
12.     }
13.     bool isHappy(int n)
14.     {
15.         //通过鸽巢原理可以证明一定成环，所以可以利用快慢双指针来解决这个问题
16.         //注意slow 与 fast 的初始化！
17.         int slow = n , fast = getbit(n);
18.         //当slow 与 fast 相遇的时候，一定在环中相遇，此时只需要判断相遇的值便可
19.         while(slow!=fast)
20.         {
21.             //slow 一次走一步
22.             //fast 一次走两部
23.             slow = getbit(slow);
24.             fast = getbit(getbit(fast));
25.         }
26.         return slow==1;
27.     }

复制代码

题4 盛最多水的容器：

11. 盛最多水的容器 - 力扣（LeetCode）

数据范围：

例子：

思索：

解法一：暴力解法
将所有两两组合的环境均列举出来，找到其中的最大值即可；此处的数据量约有 10万，使用暴力解法的时间复杂度为 O(N^2) ,肯定会超时的，不外此处我们还是实验一下用暴力解法是否能过：

测试用例能通过，但是提交之后：

解法二：使用单调性使用双指针
为什么会想到用单调性？

• 假如想要找到两数相乘再乘以其底面积的最大值，肯定是从左边地区中找一个最大的乘以右边地区中最大的数；使用双指针一个从左边开始，一个从右边开始，谁小谁就往自己所在的方向移动；而假如有一个木桶，它的板高度不一样，它所能所能存多少水是由最短的板决定的，以是我们该用短板才会有效果，而桶底也是变革的，以是还需要一个变量来纪录体积；
  

例子：

思绪总结：界说两个指针left right ,根据这两个指针指向的数据，纪录盘算出来的体积，谁小谁移动，循环下去更新得到的最大值；循环条件：left<right;
参考代码：
 

1.     int maxArea(vector<int>& height)
2.     {
3.         //体积由短板决定
4.         int left = 0 , right = height.size()-1 ,ret = INT_MIN;
5.         while(left<right)
6.         {
7.             //体积 = 短板长度*底面积
8.             int v = (height[left]<height[right]?height[left] : height[right]) * (right-left);
9.             ret = max(ret , v);
10.             //谁小谁移动
11.             if(height[left]>height[right]) right--;
12.             else left++;
13.         }
14.         return ret;
15.     }

复制代码

题5 有效三角形的个数：

611. 有效三角形的个数 - 力扣（LeetCode）
题干：

数据范围：

例子：

思索：

本题无非就是摆列出所有的三个数，然后判定这三个数可否构成三角形；
Q：怎样判定三个数可否构成三角形？

• 起首会想到的是“双方之和大于第三边”，让三个数两两组合然后与第三个数比力，看是否符合就行，但是这种判定方式需要判定三次，服从上有点低，有没有高效点的判定方法？
  

第二种判定方法：让较小双方相加与最长边比力，假如是大于则就可以构成三角形；
由于最长边肯定是大于较小边的（别的两个环境），以是只要保证让较小双方相加大于最长边便可，图解如下：

而对于摆列，起首我们肯定会想到的是暴力解法，使用循环摆列出所有的环境，然后判定，这种方法的时间复杂度为O(N^3)，先试一下暴力解法可否通过：

使用暴力解法，测试用例可以通过，但是提交：

不能使用暴力解法办理，还能怎么做？
我们前面曾说，判定两个数能够构成三角形，假如得到了这三个数的巨细关系，可以拿较小的两个数与最大的那一个数进行比力，不大概每次拿到三个数就先比力巨细吧？暴力摆列依然是个痛处，既然在比力的时间就要知道数据的巨细关系，那么我们可以先对数据进行排序，使用数据的单调性以及三指针；

   

• 当 b + c > a 时（即 b 和 c 指向的数据之和大于 a 指向的数据），这三个数肯定可以构成三角形。此时，区间 [b+1, c-1] 内的数据均大于 b，且与 c 相加后仍满意大于 a 的条件，那么就有（c-1-b+1）个数符合要求，使用变量纪录；然后 c 减 1，继承在下一个区间进行判定
  
• 当 b + c < a 时（即 b 和 c 指向的数据之和小于 a 指向的数据），这三个数无法构成三角形。此时，区间 [b+1, c-1] 内的数据均小于 c 指向的数据，不符合要求，无需纪录，直接让 b 加 1，继承在下一个区间中寻找符合条件的组合。
  

  最大的数a 从右往左遍历，b初始化为0，c初始化为a-1;
这就是解法二：使用单调性，使用双指针方法来办理题目，稍微总结一下：

• 1、先固定最大的数
  
• 2、在最大的数的左区间中，使用双指针算法，快速统计出符合要求的三元组的个数；
  

举个例子：

参考代码：

1.     int triangleNumber(vector<int>& nums)
2.     {
3.         //先对数据进行排序处理
4.         sort(nums.begin() , nums.end());
5.         int n = nums.size();
6.         int a = n-1 , ret = 0;
7.         //指向最大的指针
8.         for( ; a>=2;a--)
9.         {
10.             int b = 0, c = a-1;
11.             //让较小的两个
12.             while(b<c)
13.             {
14.                 if(nums[b]+nums[c]>nums[a]) //b->[b,c-1] 区间中的数据均合理
15.                 {
16.                     ret+=(c-1-b+1);
17.                     c--;//去下一个区间
18.                 }
19.                 else //不符合要求，那么c->[b+1,c] 中的均不符合
20.                 {
21.                     b++;
22.                 }
23.             }
24.         }
25.         return ret;
26.     }

复制代码

题6 查找总代价为目标值的两个商品：

LCR 179. 查找总代价为目标值的两个商品 - 力扣（LeetCode）
标题：

数据范围：

例子：

思索：

方法一：暴力解法
将所有的两个数的组合列举出来然后进行比力
伪代码：

可以试一下用暴力解法可否通过算法：

提交：

暴力解法不可；
方法二：题干中说过price 数组中的数据为升序，我们可以使用好单调性；开始想到的大概是二分算法，但是此处不保举使用二分，我们可以使用单调性+双指针来办理；
设置两个指针：left 与right , 让left 指向最左的数据，让right 指向最大的数据，假如left + right 的效果大于 target ，那么right--;假如left + right 的效果小于target 那么left++;图解如下：

总结算法逻辑：

参考代码：

1.     vector<int> twoSum(vector<int>& price, int target)
2.     {
3.         //利用数据的单调性+双指针
4.         int n = price.size();
5.         int left = 0, right = n-1;
6.         while(left < right)
7.         {
8.             if(price[left]+price[right] > target) right--;
9.             else if(price[left]+price[right] < target) left++;
10.             else return {price[left] , price[right]};
11.         }
12.         //没有找到，返回空
13.         return{};
14.     }

复制代码

题7 三数之和：

15. 三数之和 - 力扣（LeetCode）
题干如下：

数据范围：

例子：

思索：

即在数组中找到三个不重复的数据让其相加为0；
根据前面做过的题的履历，我们可以先将数据进行排序处置惩罚；
Q：怎样让找到的三个数据不重复呢？

• 可以起首将nums 中的数据进行去重处置惩罚，使用set就可以了;
  

解法一：暴力解法：排序 + 暴力摆列 + 使用set 进行去重
此处就不验证暴力解法是否能通过了，数据量有10万，时间复杂度为O(N^3) 的算法肯定会超时；
解法二：排序 +  固定一个数a ，使用双指针找到作甚-a 的两个值
这样的话，”使用双指针找到作甚-a 的两个值“ 的思绪就与题6中的思绪非常像；
Q：那么去重呢？

• 笔试中可以使用容器set进行去重，但是在口试中不保举这么做；本题，我们开始就对数据进行了排序处置惩罚，那么相同的数据就已经放在了一起；当我们找到了一个效果的时间left 和 right 该怎样移动？left 和 right 要跳过与当前所指数相同的重复的数据，继承缩小空间继承查找，同样的，我们固定的数a 也需要进行去重处置惩罚，当使用完一轮双指针算法之后，a 也需要跳过重复的数据；
  

要做到不重不漏；
参考代码：

1.     vector<vector<int>> threeSum(vector<int>& nums)
2.     {
3.         //首先先对数组进行排序
4.         sort(nums.begin(), nums.end());
5.         
6.         int n = nums.size();
7.         vector<vector<int>> ret;
8.         for(int i = 0 ;i< n; )
9.         {
10.             int left = i+1, right = n-1;
11.             while(left < right)
12.             {
13.                 int target = -nums[i];
14.                 int sum = nums[left] + nums[right];
15.                 if(sum > target) right--;
16.                 else if(sum < target) left++;
17.                 else
18.                 {
19.                     ret.push_back({nums[i], nums[left] , nums[right]});
20.                     left ++ ,right--;
21.                     //去重
22.                     while( left < right && nums[left] == nums[left-1]) left++;
23.                     while( left < right && nums[right] == nums[right+1]) right--;
24.                 }
25.             }
26.             //一轮双指针结束之后，还要对固定的数进行去重处理
27.             ++i;
28.             while(i<n && nums[i] == nums[i-1]) ++i;
29.         }
30.         return ret;
31.     }

复制代码

题8 四数之和：

18. 四数之和 - 力扣（LeetCode）
题干：

数据范围：

例子：

思索：
本题的解题思绪非常浅近：找到4个数 + 判定是否相加为target
找数就有讲求了，要么暴力摆列，要么使用比力巧妙的方法，同样的，本题要求不包罗重复的数据，我们可以思量使用set 去重；
通过数据范围就知道，我们要使用long long ；
解法一：排序 + 暴力解法 + 使用set去重
本题的数据量很大，而且要暴力摆列出4个数，实践复杂度非常高，肯定会超时，此处就不演示了；
解法二：排序 + 双指针
可以参考上题三数之和的思绪；
起首是将数据进行排序，使用数据有序的特点可以进步服从；然后是固定一个数，再固定一个数，剩下两个数使用双指针；可以理解为，我们先固定一个数a，那么标题就酿成在除了固定的的这个数中找和为 （target-a）的三个数：

末了需要做到“不重不漏”，本题会设置三个循环，两个循环用来固定两个数，一个循环实用于双指针，这三个循环都需要关注去重处置惩罚（假如不消set 去重的话）；而关于不漏，在双指针查找的过程中，我们要在left 和 right 中找到和为目标值时，不能直接竣事当前的双指针查找循环，而是要left++,right-- 且left<right ，继承查找下去；
初次实验：；

盘算目标值的时间，记得用long long!
参考代码：

1.     vector<vector<int>> fourSum(vector<int>& nums, int target)
2.     {
3.         //首先对数据进行排序
4.         sort(nums.begin() , nums.end());
6.         int n = nums.size();
7.         vector<vector<int>> ret;
9.         //固定数a
10.         for(int i = 0; i<n; )
11.         {
12.             //固定数b
13.             for(int j = i+1;j<n; )
14.             {
15.                 long long t = ( long long)target - nums[i] -nums[j];
16.                 //双指针查找
17.                 int left = j+1,right = n-1;
18.                 while(left < right)
19.                 {
20.                     int sum = nums[left] + nums[right];
21.                     if(sum > t) right--;
22.                     else if(sum < t) left++;
23.                     else
24.                     {
25.                         //将数据放入数组中
26.                         ret.push_back({nums[i] , nums[j] , nums[left] , nums[right]});
27.                         //去重
28.                         left++,right--;
29.                         while(left < right && nums[left] == nums[left-1]) left++;
30.                         while(left < right && nums[right] == nums[right+1]) right--;
31.                     }
32.                 }
33.                 //固定的第二个数的去重
34.                 ++j;
35.                 while(j<n && nums[j] == nums[j-1])j++;
36.             }
37.             //固定的第一个数的去重
38.             ++i;
39.              while(i<n && nums[i] == nums[i-1])i++;
40.         }
41.         return ret;
42.     }

复制代码

---

总结

双指针题单如下，可以自己练习：

• 283.移动零
  
• 1089. 复写零
  
• 202. 快乐数
  
• 11. 盛最多水的容器
  
• 611. 有效三角形的个数
  
• LCR 179. 查找总代价为目标值的两个商品
  
• 15. 三数之和
  
• 18. 四数之和
  

颠末以上练习，我们应该可以显然地感受到这类题的特点：从两端向中心出发，逐渐缩小数据范围，必要时，还可以借助于数据的单调性一起使用；借助于单调性会极大地进步代码的服从；