本文主要是介绍【LeetCode热题100】双指针，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
class Solution {
public:void moveZeroes(vector<int>& nums) {int dst = -1,cur = 0;while(cur<nums.size()){if(nums[cur] == 0){cur++;}else{swap(nums[dst+1],nums[cur]);cur++;dst++;}}}
};题目分析：对于数组分块/数组划分的问题，我们可以使用双指针算法进行求解（这道题的“指针”是数组下标）。我们使用两个“指针”dst和cur，将数组划分为三个区间：[0,dst]已处理过且不为0的区间、[dst+1,cur-1]已处理过且为0的区间、[cur,n-1]待处理的区间。两个指针的作用：cur--从左往右扫描数组，遍历数组；dst--已处理的区间内，非零元素的最后一个位置。cur向后依次遍历，可能会有两种情况：1.cur指向的元素为0，cur++ 2.cur指向的元素不为0，swap(nums[dst+1],nums[cur])，cur++，dst++。由于刚开始时没有已处理的区间，所以dst=-1，cur=0。
class Solution {
public:void duplicateZeros(vector<int>& arr) {//1.找到要复写的最后一个数int cur = 0,dst = -1;while(cur < arr.size()){if(arr[cur] == 0) dst+=2;else dst++;if(dst >= arr.size()-1){break;}cur++;}//处理一下边界情况：dst加了两下，加过了if(dst == arr.size()){arr[dst-1]=0 ;dst-=2;cur--;}//2.从后向前复写while(cur >= 0){if(arr[cur] == 0){arr[dst]=arr[dst-1]=0;dst -= 2;cur--;}else{arr[dst]=arr[cur];dst--;cur--;}}}
};题目分析：这道题是对数组元素进行操作，可以考虑双指针算法。整体思路就是先根据“异地”操作，然后优化成双指针下的“就地”操作。我们首先想到的是另外创建一个数组，进行异地操作，一个指针cur指向原数组，另一个指针dst指向新建数组，cur依次遍历每一个数，按照要求在新建数组进行复写。然而，这样的做法明显不符合“就地操作”的要求，因此，我们需要让cur和dst都指向原数组，如果它们都指向了起始位置，这样遇到复写0之后就会覆盖后面的元素，肯定会出问题。所以我们需要从后往前复写，dst需要指向数组最后一个元素，cur要指向最后一个“复写”的数，因此，我们总共有两步：1.先找到最后一个“复写”的数 2.“从后向前”完成复写操作。经过多次实践，可以通过如下方法找到最后一个复写的数：1）先判断cur位置的值 2）决定dest向后移动一步或者两步 3）判断一下dest是否已经结束 4）cur++ 在开始之前，我们需要先让dst指向-1，cur指向0（因为最终dst指向最后一个要复写的位置，刚开始的时候并不知道最后一个位置在哪，因此设为-1），当这个循环退出时，cur指向了最后一个“复写”的数。此外，在找最后一个要复写的数的过程中，我们还可能因为cur最后一次指向0，dst需要加两次，跳到了arr的外面，即下标为n的位置，对于这种情况，我们需要单独处理一下，让arr[n-1]=0，然后dst回退两次，cur--即可。
class Solution {
public:int bitSum(int n){int sum = 0;while(n){int lastbit = n%10;sum += lastbit*lastbit;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;}
};题目分析：给定一个正整数，按照题目给定的过程重复计算，会有两种结果：其一是这个数在某一次变成1，那么之后会一直循环1；第二种是这个数会在某个圈里无限循环，但是不是1。因此，一定会进入循环（鸽巢原理），我们可以通过判断当进入循环后，这个值是不是1来确定这个数是不是快乐数。
那么如何找到进入循环的某一个数呢？这个就需要用到快慢指针的思想：
（一）定义快慢指针
（二）慢指针每次向后移动一步，快指针每次向后移动两步
（三）判断相遇时候的值即可
class Solution {
public:int maxArea(vector<int>& height) { int max= 0;int i =0,j=height.size()-1;int v = 0;//体积while( i < j){v = (j - i) * (height[i]<height[j]?height[i]:height[j]);if(v > max) max = v;if(height[i] < height[j]) i++;else j--;}return max;}
};题目分析：第一种方法就是暴力求解，遍历每一个可能得组合，计算出它们的体积的最大值，但是这种方法是运行超时的，因此我们还要另辟蹊径。
第二种方法比较巧妙，我们先来看一个简单例子，如果数组是[6,2,5,4]，那我们先计算最外面两个数的组合：6和4，宽度是3，高度是max（6,4）=4，体积=3*4=12，我们再往里面深入，如果是4和2组合，首先它们的宽度变成2（往里深入宽度必定减少），高度变成2（高度必定是≤4，），很显然，宽度必定减少，高度最多保持不变，那么4和往里面的树组合体积必定减少，因此就不用考虑4和里面任何数的组合，所以直接忽略4（两侧--6和4中较小的那一个值），数组变成[6,2,5]，然后继续依照上面逻辑，先计算出最外侧两个数的体积，和上一个体积比较，最后直到整个数组被遍历完！
class Solution {
public:int triangleNumber(vector<int>& nums) {//1.优化sort(nums.begin(),nums.end());int size = nums.size();int fixi = size-1;int left = 0;int right = fixi-1;int ret = 0;while(fixi > 1){while(left < right){if(nums[left] + nums[right] > nums[fixi]){ret += right - left;right--;}else{left++;}}fixi--;left = 0;right = fixi-1;}return ret;}};题目分析：如果要判断的三个数是有序的（a < b < c），那么只需要判断一次即可，就是判断 a+b是否大于c，因为b+c肯定大于a，a+c也肯定大于b。
这道题有两种解法，一种是暴力解法，遍历这个数组得到三个数，依次判断是否符合，这种解法的时间复杂度很高。另外一种解法，也是利用双指针的思想，比如给出的数组是[2,3,5,5,7,8,9,12]，先固定一个最大的c，也就是最后的12，然后让left指向剩下的最小的，即2，再让right指向剩下最大的，即9，判断left+right和固定最大值c=12的大小关系，那么就有两种情况：
1.left+right>c，那么right和left与right中间的任意一个组合都符合条件，不用继续遍历中间的，符合的组数为right-left，再让right--；
2.left+right<=c，那么，left和left与right中间任意一个组合都不符合条件，left++；
当left=right后，这一回合遍历结束，再让固定的最大值c向前调整一个，然后继续上述步骤即可。
class Solution {
public:vector<int> twoSum(vector<int>& price, int target){vector<int> ret;int size = price.size();int left = 0;int right = size - 1;while(left < right){if(price[left] + price[right] < target){left++;}else if(price[left] + price[right] > target){right--;}else{return {price[left],price[right]};//隐式类型转换}}//虽然我们知道这条语句不会被执行，但是为了照顾编译器，//需要在每条返回路径上都返回return {1,1};}
};题目分析：和有效三角形的个数的思想非常类似，也是用到双指针的思想。刚开始的时候，左指针left指向数组最左，右指针right指向数组最右，整个数组是单调递增的，先判断left+right和target的关系，分为三种情况：
1.left+right > target，那么right和left与right之间的任意数之和都大于target，就没有必要继续遍历了，让right--；
2.left+right < target，那么left和left与right之间的任意数之和都小于target，也没有必要继续遍历了，让left++;
3.left+right > target，那么直接返回即可，走隐式类型转换。
需要注意的是，需要在循环外加一个return语句，这样编译器才不会报错，认为每条路径都会有返回值。
class Solution {
public:vector<vector<int>> threeSum(vector<int>& nums) {sort(nums.begin(),nums.end());int size = nums.size();vector<vector<int>> vv;for(int i = 0; i < size - 2; ){if(nums[i] > 0) break;int left = i + 1;int right = size - 1;while(left < right){if(-1 * nums[i] < nums[left] + nums[right]){right--;}else if(-1 * nums[i] > nums[left] + nums[right]){left++;}else{vv.push_back({nums[i],nums[left],nums[right]});left++;right--; //去重操作 left rightwhile(left < right && nums[left] == nums[left-1]) left++;while(left < right && nums[right] == nums[right+1]) right--;}}i++;//去重iwhile(i < size && nums[i] == nums[i-1]){i++;} }return vv;}
};题目分析：这道题依然是有两种解法：暴力解法和优化解法，
暴力解法：先对数组进行排序，然后对数组中的每三个数进行遍历，当找到三个数的符合条件后，将这三个数的组合插入set中，这样方便去重，但是暴力解法的时间复杂度是O(N3)。
优化解法：先对数组进行排序，然后固定一个数a（从最左侧开始固定），在该数后面的区间内，利用上题“双指针”算法，快速找到这个区间内和为-a的两个数。
处理细节：
1.去重：找到一种结果之后，left和right指针要跳过重复元素，直到找到下一个不重复的元素，当使用完一次双指针算法后，a也要跳过重复元素。
2.不漏：找到一种结果之后，不要“停”，缩小区间，继续寻找
3.小优化：只有a≤0时，才有可能在后面的区间找到两个数之和＝-a，因此a只需要遍历非正值即可。
class Solution {
public:vector<vector<int>> fourSum(vector<int>& nums, int target) {//1.排序sort(nums.begin(),nums.end());//2.按“双指针”查找vector<vector<int>> ret;int n = nums.size();for(int i = 0;i<n;)//固定a{for(int j=i+1;j<n;)//固定b{long long val = (long long)target - nums[i] - nums[j];int left = j+1;int right = n-1;while(left < right){int sum = nums[left] + nums[right];if(val > sum){left++;}else if(val < sum){right--;}else{ret.push_back({nums[i],nums[j],nums[left],nums[right]});left++;right--;//去重1while(left < right && nums[left] == nums[left-1]) left++;while(left < right && nums[right] == nums[right+1]) right--;} }//去重2j++;while(j < n && nums[j-1] == nums[j]) j++;}//去重3i++;while(i < n && nums[i-1] == nums[i]) i++;}return ret;}
};题目分析：这道题会借用上面三数之和的思想，首先还是对数组进行排序，然后先固定最左边第一个数a，然后从后面区间找出和为target-a的三个数，然后就是借助三数之和的思想，先固定剩下区间的第一个数b，再从剩下区间找和为target-a-b的两个数，然后继续遍历，要和三数之和一样要做到不重不漏。
这篇关于【LeetCode热题100】双指针的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
