专题一_双指针_算法专题详细总结

双指针

对撞指针：⼀般⽤于顺序结构中，也称左右指针。

快慢指针：⼜称为⻳兔赛跑算法，其基本思想就是使⽤两个移动速度不同的指针在数组或链表等序列结构上移动。

1. 移动零（easy）

「数组分两块」是⾮常常⻅的⼀种题型，主要就是根据⼀种划分⽅式，将数组的内容分成左右两部分。这种类型的题，⼀般就是使⽤「双指针」来解决。

解题思路：

1.暴力求解：

2.双指针

算法总结：

2. 复写零（easy）

1.暴力求解：

2.双指针

1).寻找最后一个进行复写的元素

2).处理边界情况

3).从后向前进行复写

优化：

3. 快乐数（medium）

1.简单证明：

2.但是我后来发现，其实只用hash表+字符串来做这题也十分简单

4. 盛⽔最多的容器（medium）

1.解法⼀（暴⼒求解）（会超时）：

2.双指针，很难想

5. 有效三⻆形的个数（medium）

1.解法⼀（暴⼒求解）（会超时）：

2.很难，很有意义的双指针

6、LCR 179.查找总价格为目标值的两个商品

1.暴力：（超时）

2.双指针（缩小范围）：

7. 三数之和（medium）

1.暴力：想都不用想 O(N^3) 绝对超时；

2.排序+双指针

8.四数之和（medium）

双指针：

算法专题——双指针，根据自己的学习总结出的多种双指针应用场景和使用方法。

一般来说，在面对数组算法题，极大可能考虑排序数组sort() 会优化时间复杂度，提高解题效率，提供解题思想，那么在数组排序后就会优先选择双指针和二分查找两种算法，今天先来介绍双指针，一般情况下，在多维时间复杂度的情况下，利用双指针可以直接降低一维时间复杂度，极大的优化了算法的性能。

双指针

常⻅的双指针有两种形式，⼀种是对撞指针，⼀种是左右指针。

对撞指针：⼀般⽤于顺序结构中，也称左右指针。

• 对撞指针从两端向中间移动。⼀个指针从最左端开始，另⼀个从最右端开始，然后逐渐往中间逼近。

• 对撞指针的终⽌条件⼀般是两个指针相遇或者错开（也可能在循环内部找到结果直接跳出循环），也就是：

◦ left == right （两个指针指向同⼀个位置）

◦ l eft > right （两个指针错开）

快慢指针：⼜称为⻳兔赛跑算法，其基本思想就是使⽤两个移动速度不同的指针在数组或链表等序列结构上移动。

这种⽅法对于处理环形链表或数组⾮常有⽤。

其实不单单是环形链表或者是数组，如果我们要研究的问题出现循环往复的情况时，均可考虑使⽤快慢指针的思想。

快慢指针的实现⽅式有很多种，最常⽤的⼀种就是：

• 在⼀次循环中，每次让慢的指针向后移动⼀位，⽽快的指针往后移动两位，实现⼀快⼀慢。

1. 移动零（easy）

「数组分两块」是⾮常常⻅的⼀种题型，主要就是根据⼀种划分⽅式，将数组的内容分成左右两部分。这种类型的题，⼀般就是使⽤「双指针」来解决。

解题思路：

1.暴力求解：

两层循环嵌套，第一层来寻找0的位置，第二层将所有元素往前移动，最后补0；

2.双指针

数组分块，首先就是双指针，
[0,dest] 非0 [dest+1,cur-1] 全部为0 [cur,n-1] 待处理
刚开始让dest=-1，cur=0，当nums[cur]==0 就一直cur++；当cur！=0 就swap(++nums[dest],nums[cur])；

class Solution {
public:void moveZeroes(vector<int>& nums) {int left=-1,right=left+1;int n=nums.size();for(;right<n;){if(nums[right]!=0){swap(nums[++left],nums[right++]);}else right++;}}
};

算法总结：

这个⽅法是往后我们学习「快排算法」的时候，「数据划分」过程的重要⼀步。如果将快排算法拆解的话，这⼀段⼩代码就是实现快排算法的「核⼼步骤」。

2. 复写零（easy）

1.暴力求解：

两层循环嵌套，第一层找0，第二层while将从0这个位置开始的元素全都往后移动。

class Solution {
public:void duplicateZeros(vector<int>& arr) {int left=0;int n=arr.size();for(;left<n;left++){if(arr[left]==0){int right=n-1;while(right>left){arr[right]=arr[right-1];right--;}left++;}}}
};

显然时间复杂度是O(N^2) ，那么就要想办法来进行优化，可以考虑双指针，就能直接降低一维时间复杂度，变成O(N);

2.双指针

1).寻找最后一个进行复写的元素

利用双指针，cur=0，dest=-1，只要nums[cur]==0 dest就走两格；否则 dest走一格；但是无论怎么样cur都走一格。直到dest到达结尾处n-1 停止，即判断dest>=n-1 处 break；

2).处理边界情况

当dest==n 时，说明nums[cur]此时对应的0，并且dest越界到n处，那么此时nums[n] nums[n-1] 都要复写成0，那么就直接进行修改arr[n-1]=0;cur-=1;dest-=2;

3).从后向前进行复写

在left开始就判断arr[left]==0 如果是，就用right指针，从arr尾部开始，依次把元素往后移，直到right==left停止，这样当left到达n-1时结束

优化：

1.从左往右开始寻找，找到最后一个要被复写的值的下标cur，有两种情况，1.当dest自然在n-1位置停下，这个时候就要判断if(dest>=n-1) 就break；2.当最后cur遇到一个0，让dest++两下直接越界到n处，那么这个时候最后复写的就是0元素，那么n-1处跟n处都要被复写成0，所有，在这种边界条件下就直接进行修改，arr[n-1]=0,cur-=1,dest-=2;在完成正常的复写操作。

2.最后就是复写操作，在arr[cur]==0 的时候arr[dest--]=arr[cur];就复写一次，否则就复写两次，cur都要进行一次-- 边界情况就是cur要>=0,在cur==0时任然完成一次复写

class Solution {
public:void duplicateZeros(vector<int>& arr) {int n=arr.size();//1.找到最后一个复写的数int cur=0,dest=-1;while(cur<n){if(arr[cur]) dest++;else dest+=2;//当dest==n-1位置的时候就说明，dest已经可以结束运动了if(dest>=n-1) break;cur++;}//处理边界情况if(dest==n){arr[n-1]=0;cur-=1;dest-=2;}//从后向前完成复写操作while(cur>=0){if(arr[cur]) arr[dest--]=arr[cur];else{arr[dest--]=0;arr[dest--]=0;}cur--;}}
};

实际上这题双指针并不好想，所以一定要多总结，这题双指针优化还是挺明显的。

3. 快乐数（medium）

快乐数，实际上就是对于一个数字的每一位进行拆分，平方后相加继续拆分，看到这种拆分确实可以用双指针的思想，一直拆分相加，可以想到，后面会是相当于一个循环链表一样的题目，判断是否纯在循环点，判断最后ret是否等于1，如果是就返回true ；否则返回false；

1.简单证明：

a. 经过⼀次变化之后的最⼤值⼤ 9 9^2 * 10 = 810 ( 999999999 )，也就是变化的区间在 2^31-1=2147483647 。选⼀个更⼤的最 [1, 810] 之间；

b. 根据「鸽巢原理」，⼀个数变化 811 次之后，必然会形成⼀个循环；

c. 因此，变化的过程最终会⾛到⼀个圈⾥⾯，因此可以⽤「快慢指针」来解决。

解法（快慢指针）：

算法思路：根据上述的题⽬分析，我们可以知道，当重复执⾏ x 的时候，数据会陷⼊到⼀个「循环」之中。⽽「快慢指针」有⼀个特性，就是在⼀个圆圈中，快指针总是会追上慢指针的，也就是说他们总会相遇在⼀个位置上。如果相遇位置的值是 1 ，那么这个数⼀定是快乐数；如果相遇位置不是 1 的话，那么就不是快乐数。

补充知识：如何求⼀个数n每个位置上的数字的平⽅和。

a. 把数 n 每⼀位的数提取出来：

循环迭代下⾯步骤：

i. int t = n % 10 提取个位；

ii. n /= 10 ⼲掉个位；直到 n 的值变为 0 ；

b. 提取每⼀位的时候，⽤⼀个变量 t mp = tmp + t * t C++算法代码： tmp 记录这⼀位的平⽅与之前提取位数的平⽅和。

class Solution 
{public:int bitSum(int n) // 返回 n 这个数每⼀位上的平⽅和
{ int sum = 0;while(n){int t = n % 10;sum += t * t;n /= 10;}return sum;}bool isHappy(int n) {int slow = n, fast = bitSum(n);while(slow != fast){slow = bitSum(slow);fast = bitSum(bitSum(fast));}return slow == 1;}};

2.但是我后来发现，其实只用hash表+字符串来做这题也十分简单

class Solution {
public:bool isHappy(int _n) {unordered_set<int> hash;while(1){string s=to_string(_n);int n=s.size();vector<int> v;int ret=0;for(int i=0;i<n;i++){ret+=pow((s[i]-'0'),2);}if(hash.count(ret)) return false;hash.insert(ret);if(ret==1) return true;_n=ret;}return false;}
};

判断这个数字每一位平方和是否最后相加等于1，那么就把每次算出的ret都放入hash进行判断，如果存在重复的数字，说明死循环了；否则就是快乐数

4. 盛⽔最多的容器（medium）

这一题是真的经典，很好的说明了双指针的作用。哪怕是花了一天事件弄懂这一题也是值得的。

1.解法⼀（暴⼒求解）（会超时）：

算法思路：枚举出能构成的所有容器，找出其中容积最⼤的值。

◦ 容器容积的计算⽅式：设两指针 i , j ，分别指向⽔槽板的最左端以及最右端，此时容器的宽度为容器的⾼度由两板中的短板决定，因此可得容积公式： j - i 。由于 v = (j - i) * min( height[i], height[j])

 class Solution {public:int maxArea(vector<int>& height) {int n = height.size();int ret = 0;// 两层for 枚举出所有可能出现的情况for (int i = 0; i < n; i++) {for (int j = i + 1; j < n; j++) { // 计算容积，找出最⼤的那⼀个
ret = max(ret, min(height[i], height[j]) * (j - i));
return ret;}}}};

2.双指针，很难想

1.就是暴力，两层循环嵌套，想都不要想肯定超时

2.那么就考虑利用双指针，我们定义left和right，分别从左往右，和从右往左开始遍历，这样整个遍历完，时间复杂度都只是O(N)，
有题知道，V=H*W，那么每次移动W宽是必定会减少的，，就有三种情况，

1).H高也减少，V减少,不考虑 .

2).H不变，体积也会减少，不考虑。

3).H变大，那么就可以从这里下手，那么，我们每次判断就是判断left和right 谁先移动，这样我们就考虑每次移动的指针都是较小的那个，然后计算出体积再次进行比较，如果此时算出的体积>ret 那么就更新ret，直到left==right时停止循环，不在进行计算。会得到最大的ret。

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

5. 有效三⻆形的个数（medium）

这一题确实也很难，但还是那句话，如果花一天事件去学习，那也是值得的。

1.解法⼀（暴⼒求解）（会超时）：

算法思路：三层 for 循环枚举出所有的三元组，并且判断是否能构成三⻆形。虽然说是暴⼒求解，但是还是想优化⼀下：判断三⻆形的优化：

▪ 如果能构成三⻆形，需要满⾜任意两边之和要⼤于第三边。但是实际上只需让较⼩的两条边之和⼤于第三边即可。

▪ 因此我们可以先将原数组排序，然后从⼩到⼤枚举三元组，⼀⽅⾯省去枚举的数量，另⼀⽅⾯⽅便判断是否能构成三⻆形。

class Solution {public:int triangleNumber(vector<int>& nums) {// 1. 排序sort(nums.begin(), nums.end());int n = nums.size(), ret = 0;// 2. 从⼩到⼤枚举所有的三元组for (int i = 0; i < n; i++) {for (int j = i + 1; j < n; j++) {for (int k = j + 1; k < n; k++) {// 当最⼩的两个边之和⼤于第三边的时候，统计答案if (nums[i] + nums[j] > nums[k])ret++;} }}return ret;}};

2.很难，很有意义的双指针

1.第一步肯定就是暴力，但是如果想到暴力求解每次都枚举每一种情况的话，就要用i,j,k三种来嵌套循环，是O(N^3);绝对会超时

2.那么就要来考虑优化，本来是双指针专题，一直都想不到好的解决办法，不管是把left放在0 right=1，来枚举第三个数，就又变成了暴力，那么这种肯定不可取。

3.对于确定能构成三角形，有一个小demo 就是能确保a<=b<=c 的情况下，a+b>c,那么在剩下的判断中，无论是a+c 还是 b+c 那都是妥妥的大于第三个数，因为里面c最大，那么我们只需要判断，在有序的a<b<c 里面，a+b>c成立，就可以判断能构成三角形。

4.那么此时，为了得到比较大的优化程度，我们设left=0，end=n-1,right=end-1,将end固定到最大值的位置，right=end-1处，来进行判断，使left++来进行移动，只要有满足nums[left]+nums[right]>nums[end]的值，就可以确保，left 至 right 之间的所有值都能加上nums[right] > nums[end] 那么就可以一次性算出这里面满足条件的个数ret+=right-left; 这是 a+b>c的情况

5.在计算出left 到 right 满足条件的次数之后，那么right--，来缩小范围，如果不能满足，就left++，直到满足或left==right为止，重复上面步骤，就能够得到所有关于end对应元素的所有情况，那么此时在while外end--，更新end right 和 left 重复以上情况，直到最后只剩下三个元素进行比较，完成所有情况的遍历，这种时间复杂度也是质的飞跃，：快排O(NlogN+N^2) 比 O(N^3) 快很多很多倍

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

6、LCR 179.查找总价格为目标值的两个商品

还是比较简单的，很容易想到的双指针，就是left++，right-- 找趋近的值

1.暴力：（超时）

算法思路：两层 for 循环列出所有两个数字的组合，判断是否等于⽬标值。

算法流程：两层 for 循环： ◦ 外层 for 循环依次枚举第⼀个数 a ；

◦ 内层 for 循环依次枚举第⼆个数 b ，让它与 a 匹配； ps ：这⾥有个魔⻤细节：我们挑选第⼆个数的时候，可以不从第⼀个数开始选，因为 a 前⾯的数我们都已经在之前考虑过了；因此，我们可以从 a 往后的数开始列举。

◦ 然后将挑选的两个数相加，判断是否符合⽬标值。

2.双指针（缩小范围）：

总结：1.跟前面的双指针一样，left=0,right=n-1,这样就可以保证在nums[left] + nums[right] 这个范围里面进行调整，如果小于target ，left++；如果大于target，right--。这样不断地缩小关于target的范围，进行调整

class Solution {
public:vector<int> twoSum(vector<int>& price, int target) {int n=price.size();int left=0,right=n-1;vector<int> v;while(left<right){if(price[left]+price[right]==target){v.push_back(price[left]);v.push_back(price[right]);return v;} else if(price[left]+price[right]>target){right--;}else left++;}return v;}
};

7. 三数之和（medium）

重头戏，还是那句话，花一天时间学会这一天，双指针基本也没啥问题了，有很多细节需要注意。

通过第6题，可以理解为双数之和，这里的三数之和，只不过是多了一个固定的i而已。

特别锻炼代码能力！！！

1.暴力：想都不用想 O(N^3) 绝对超时；

2.排序+双指针

如果数组有必要排序，就排序，数组一旦有序，就要想二分或者双指针，但是能用双指针就不用二分，因为双指针就能直接降调一维时间复杂度。

1.这题仍然是固定的找三数问题，那么绝对是固定一个指针，让另外两个指针，left=i+1,right=n-1;首先就考虑两个问题，

1.是考虑在left 跟 right 区间进行查找的时候，找到了b=nums[left]+nums[right];=-nums[i] 的结果时，不能退出，仍然要继续进行查找，那么就要保证left++,right--; 对于int a=nums[i]; 的设定，就要考虑left right 指针的移动，当-a>b 的时候b就太小了，left++ ；当-a<b 的时候就是b太大了要right--；这样做到不漏数据

2.做到去重数据：
1.利用unordered_set<vector<int>> hash 进行去重，但是这样过于无脑，不用考虑left和right跳过重复元素，i跳过重复元素的情况

2.每次在找到有满足数据的left 和 right 时，只是将所有数据都存入v里面，考虑left right i 跳过重复数据就又能有常数级的优化（小demo）跳过重复元素就left++ right-- 那么在这之前就要考虑while(left<right&&nums[left]==nums[left+1]) left++;
while(right>left&&nums[right]==nums[right-1]) right--;
致命的问题就是对于left<right 防止当数组里面数据为全0 的时候 left 和 right 就都会越界，对于i while(i<n-1&&nums[i]==nums[i+1]) i++; 进行去重的时候，要注意边界条件，i<n-1 防止i越界

class Solution {
public:vector<vector<int>> threeSum(vector<int>& nums) {int n=nums.size();sort(nums.begin(),nums.end());vector<vector<int>> ret;for(int i=0;i<n-1;i++){if(nums[i]>0) break;int left=i+1,right=n-1;int a=nums[i];while(left<right){vector<int> v;int b=nums[left]+nums[right];if(a==-b){v.push_back(nums[i]);v.push_back(nums[left]);v.push_back(nums[right]);//对left 和 right 去重while(left<right&&nums[left]==nums[left+1]) left++;while(right>left&&nums[right]==nums[right-1]) right--; left++,right--;ret.push_back(v);}else if(-a>b) left++;else right--;}// 对i去重while(i<n-1&&nums[i]==nums[i+1]) i++;}return ret;}
};

8.四数之和（medium）

如果真的学会了三数之和，那么真的希望你能自己动手去画图调试四数之和，来独立完成这一题，只不过多了一个j来多固定一个数，跟三数之和完全就是一模一样！

特别锻炼代码能力！！！

双指针：

四数之和跟三数之和一样，就只是要考虑a=target-b 和开 long long 不然会爆数据

class Solution {
public:vector<vector<int>> fourSum(vector<int>& nums, int target) {int n=nums.size();sort(nums.begin(),nums.end());vector<vector<int>> ret;for(int i=0;i<=n-4;i++){for(int j=i+1;j<=n-3;j++){long long a=nums[i]+nums[j];int left=j+1,right=n-1;while(left<right){long long b=nums[left]+nums[right];if(a==target-b){ret.push_back({nums[i],nums[j],nums[left],nums[right]});while(left<right&&nums[left]==nums[left+1]) left++;while(left<right&&nums[right]==nums[right+-1]) right--;left++,right--;}else if(a<target-b) left++;else right--; }while(j<=n-3&&nums[j]==nums[j+1]) j++;}while(i<=n-4&&nums[i]==nums[i+1]) i++;}return ret;}
};

我觉得对我自己是有很大提升的，希望对你也有帮助！~