【算法】双指针-OJ题详解1

移动零（点击跳转）

原理讲解

因此我们定义两个指针：

• cur：遍历数组
• dest：已处理的区间内，最后一个非零元素的位置

这样就把数组划分成三块区间：
[0 , dest] 、[dest+1 , cur-1] 、[cur , size-1]
分别对应：
非零元素、零、待处理

具体操作：
cur遍历过程中

• 遇到0元素
  cur++;
• 遇到非0元素
  swap(dest+1，cur); //swap数组中下标为dest+1和cur的元素
  dest++;cur++;

代码实现

void moveZeroes(vector<int>& nums) {int dest = -1;int cur = 0;while (cur < nums.size()){if (nums[cur])swap(nums[++dest], nums[cur]);cur++;}
}

复写零（点击跳转）

原理讲解

这道题首先要想到从后向前遍历，因为如果从前向后遍历，会覆盖掉后面的值，较难操作，因此：

第一步找到最后一个数，可以用快慢指针来实现：cur指针、dest指针。前者从前向后遍历，后者根据前者位置的值走1步或2步，具体如下：

• 先判断cur位置的值
• 若cur位置的值非0，dest向后移动一步；若cur位置的值为0，dest向后移动2步
• 判断dest位置是否到了结束的位置
• cur++

代码实现

void duplicateZeros(vector<int>& arr) {int dest = -1;int cur = 0;//找到最后一个数while (cur < arr.size()){if (arr[cur])dest++;elsedest += 2;if (dest >= arr.size() - 1)break;cur++;}
//处理特殊情况：cur指向的最后一个数是0，dest越界if (dest == arr.size()){arr[dest - 1] = 0;cur--;dest -= 2;}
//复写while (cur >= 0){if (arr[cur])arr[dest--] = arr[cur--];else{arr[dest--] = 0;arr[dest--] = 0;cur--;}}
}

快乐数（点击跳转）

原理讲解

最后一定会成环（可以证明，用鸽巢原理）
因此可以通过判断环的起点是否为1，决定返回true还是false

→ 快慢指针
快慢指针有⼀个特性，就是在⼀个圆圈中，快指针总是会追上慢指针的，也就是说他们总会相遇在⼀个位置上。就本题而言，如果相遇位置的值是 1 ，那么这个数⼀定是快乐数；如果相遇位置不是 1 ，那么就不是快乐数。

代码实现

//求x每一位数的平方和int SqSum(int x){int ret = 0;while(x){int n = x%10;ret += n*n;x/=10;}return ret;}bool isHappy(int n) {int slow = n,fast = SqSum(n);//fast不能设成n，否则进不了循环while(slow != fast){slow = SqSum(slow);fast = SqSum(SqSum(fast));}return slow==1;}

盛最多水的容器（点击跳转）

原理讲解

我们首先想到的大概率是两层循环暴力枚举，但是复杂度高，这道题不能通关

那应该如何解这题呢？
首先，容器的容积（这道题只考虑面积）是S = h * w
h表示高度，即height[?]
w表示宽度，即两条垂线间隔的距离

为了方便叙述，我们假设左边边界height[left]小于右边边界height[right]。

如果此时我们固定⼀个边界，改变另⼀个边界，水的容积会有如下变化形式：

• 容器的宽度w一定变小。
• 由于左边界较小，决定了水的高度。①如果改变左边界，新的水面高度不确定，但是一定不会超过右边的柱子高度，因此容器的容积可能会改变（可能变大、变小、不变）。
• ②如果改变右边界，无论右边界移动到哪里，新的水面的高度一定不会超过左边界，也就是不会超过现在的水面高度，但由于容器的宽度减小，因此容器的容积⼀定会变小的。

所以我们可以舍去情况②，只需要讨论情况①（因为我们的目的是求最大的容积）

因此，我们定义两个指针left和right，然后比较height[left] 和 height[right]，移动height小的位置的指针，循环这个过程，期间产生的所有的容积里的最大值，就是要return的最终答案

代码实现

    int maxArea(vector<int>& height) {int left = 0;int right = height.size()-1;int _max = 0;while(left < right){int tmp = (right-left)*min(height[right],height[left]);_max = max(_max,tmp);if(height[left] < height[right])left++;elseright--; }return _max;}

有效三角形的个数（点击跳转）

原理讲解

我们小学五年级都学过，三角形的三条边必须满足：任意两边之和大于第三边、任意两边之差小于第三边~

假设三角形三条边长度分别为：a, b, c

• 方法① a+b < c ; a+c < b ; b+c < a

• 方法② 在①的基础上优化：先排序，a ≤ b ≤ c，只需要判断 a+b > c即可

解法一：三层循环暴力枚举 → O(n³)

解法二：利用（排序后）单调性，用双指针算法来解决。 → O(n²)

• 先固定最大的数
• 在最大数的左边区间内，用双指针算法，快速统计出符合要求的另外两个数:
• • 如果 nums[left] + nums[right] > nums[max]，说明 [left, right - 1] 区间上的所有元素均可以与 nums[right] 构成比nums[max] 大的二元组，此时满足条件的有 right - left 种；此时 right 位置的元素的所有情况相当于全部考虑完毕， right-- ，进入下一轮判断
• • 如果 nums[left] + nums[right] <= nums[max]，说明 left 位置的元素是不可能与 [left + 1, right] 位置上的任意元素构成满足条件的二元组，left++ 进入下一轮循环
• 向左移动最大数，循环上面的过程

代码实现

    int triangleNumber(vector<int>& nums) {int left,right;int cmax = nums.size() - 1;int ret = 0;sort(nums.begin(),nums.end());while (cmax > 1) {left = 0;right = cmax-1;while (left < right) {if (nums[left] + nums[right] > nums[cmax]) {ret+=(right-left);right--;     } else {left++;}}cmax--;//向左移动最大数}return ret;}

查找总价值为目标值的两个商品（点击跳转）

原理讲解

类比上面《有效三角形的个数》，会发现利用单调性同样很香：利用对撞指针优化时间复杂度

• 初始化 left ， right 分别指向数组的左右两端
• 接下来无非三种情况：
• • price[left] + price[right] == target，说明找到了，跳出循环返回即可
• • price[left] + price[right] > target，说明两数之和大了，right–
• • price[left] + price[right] < target，说明两数之和小了，left++

代码实现

    vector<int> twoSum(vector<int>& price, int target) {int left = 0,right = price.size()-1;vector<int> ret;while(left < right){if(price[left] + price[right] == target){ret.push_back(price[left]);ret.push_back(price[right]);break;}else if(price[left] + price[right] > target)right--;elseleft++;}return ret;}

或者不需创建vector直接返回：

    vector<int> twoSum(vector<int>& price, int target) {int left = 0,right = price.size()-1;while(left < right){if(price[left] + price[right] == target)return {price[left] , price[right]};else if(price[left] + price[right] > target)right--;elseleft++;}return {-1};//注意这里必须return一个数组，目的是照顾编译器，否则编译不通过}

三数之和（点击跳转）

原理讲解

我们可以利用在两数之和那道题的双指针思想，来对暴力枚举做优化：

• 先排序
• 然后固定一个数 a
• 在这个数后面的区间内，利用双指针快速找到两个数之和等于 -a 即可

但是要注意的是，这道题需要有去重操作~
（除了用set，我们可以自己实现）

• 找到一个结果之后， left 和 right 指针要跳过重复的元素；
• 当用完⼀次双指针算法之后，固定的 a 也要跳过重复的元素。

代码实现

    vector<vector<int>> threeSum(vector<int>& nums) {sort(nums.begin(),nums.end());int i =0,left,right;vector<vector<int>> vv;while(i < nums.size()-2){if(nums[i] > 0)break;//left+rightleft = i+1;right = nums.size()-1;while(left < right && right < nums.size()){if(nums[left] + nums[right] == -nums[i]){vv.push_back({nums[i],nums[left],nums[right]});left++;right--;while(left < right && right < nums.size()&&nums[left] == nums[left-1])left++;//left跳过重复元素while(left < right && right < nums.size()&&nums[right] == nums[right+1])right--;//right跳过重复元素}else if(nums[left] + nums[right] > -nums[i])right--;elseleft++;}i++;while(nums[i] == nums[i-1] && i<nums.size()-2)++i;//“固定”的数跳过重复元素}return vv;  }

四数之和（点击跳转）

原理讲解

这道题和上面的《三数之和》几乎一模一样，区别在于多了一层

• 固定一个数a
• 在这个数 a 的后面区间上，利用「三数之和」找到三个数，使这三个数的和等于 target - a 即可

代码实现

    vector<vector<int>> fourSum(vector<int>& nums, int target) {sort(nums.begin(),nums.end());vector<vector<int>> vv;int i=0,j,left,right;while(i<nums.size()){j = i+1;while(j<nums.size()){left = j+1;right = nums.size()-1;long long aim =  (long long)target-nums[i]-nums[j];//有些用例不强转会越界while(left<right){int sum =nums[left]+nums[right];if(sum == aim){vv.push_back({nums[i],nums[j],nums[left],nums[right]});left++;right--;while(left<right && nums[left] == nums[left-1])left++;while(left<right && nums[right] == nums[right+1])right--;}else if(sum < aim)left++;elseright--;}++j;while(j < nums.size() && nums[j] == nums[j-1])++j;}++i;while(i<nums.size() && nums[i] == nums[i-1])++i;}return vv;}