算法练习——双指针

前言：大佬写博客给别人看，菜鸟写博客给自己看，我是菜鸟。

学前须知（对自己）：这里的指针不一定指地址！也可能是数组下标。

1：移动零(双指针)

题目要求：

解题思路：

这道题的思路与先前快速排序中的lumoto法及其类似，只不过先前是通过双指针在数组中寻找基准值，这里是通过双指针将大于0的数排列在前。可以看到思路是完全相似的，不过是要求不一样。

在这里我们定义两个指针：

cur：当前指针的位置，初始值定义为0；

dest：需要替换数据的位置，初始值定义为-1；

让cur去遍历整个数组。

循环内，去寻找数组中不为0的数字，

若满足条件(不为零)，让dest++，随后与cur位置的数据进行交换。

若不满足条件，则让cur++，以此循环，直至cur遍历完整个数组。

代码实现：

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

2：复写零(双指针)

题目要求：

解题思路：

题目要求我们在原数组上进行修改，这说明一定涉及①：数据的交换②：数据向后平移。

此题要求复写零，那么不可能是数据的交换，则一定考虑数据的平移。但是仅仅从左往右遍历数组，然后平移数据，会丢失数组中原有的数据，因此需要从后往前遍历，以此平移数据同时添0。

既然同样是双指针的思路，那么如何正确找到两个指针的起始位置呢？

同样以 cur 和 dest 来命名，他们的初始值分别为 0 ，-1；

当 cur 当前数据非零时，dest++；

当 cur 当前数据为零时，dest+=2；

然后判断当前 dest 是否已经超过或者等于数组长度，若满足则停止循环，不满足则cur++；

如果仅仅是题目中的案例，上述过程已经能正确找到 cur 和dest的位置，但有一种情况例外，那就是：dest 超出了数组，这种情况需要单独考虑。

已如下数组为例：[8,4,5,0,0,0,0,7];

如果按照上述过程，最终 cur 和 dest 的位置会来到如图所示处。

此时 dest 已经越过数组，因此我们所要作的，就是：将 dest -1 的位置置为 0，

同时将 dest -= 2， cur--即可。

注：思考为什么将dest -1 置为 0？

答：之所以为产生越界，是因为 cur 位置当前数据为0，因此 dest 多加了一次，才会导致越界，说明 dest 与 dest +1 的位置原本都应该为 0，但是数组越界了，所以只有dest位置的数据为0，因此需要将数组末尾置为0。

简单来说，针对越界这种特殊情况，我们手动进行了一次操作，即在数组末尾插入了零。

代码实现：

void duplicateZeros(vector<int>& arr) {int cur = 0, dest = -1;size_t n = arr.size() - 1;while(cur <= n ){if(arr[cur] == 0){dest += 2;}else{dest++;}if(dest >= n){break;}cur++;}if(dest > n){arr[dest-1] = 0;dest -=2;cur--;}while(cur >= 0){if(arr[cur] != 0){arr[dest--] = arr[cur--];}else{arr[dest--] = 0;arr[dest--] = 0;cur--;}}}

3：快乐数(快慢指针)

题目要求：

解题思路：

开始讲解思路前，需要知道一点：快乐数与先前链表中通过快慢指针确定链表是否为环形链表类似。一个数。经过多次运算后，始终会等于先前运算过的一个数，然后依次往复循环。

这里我们定义：

Num_Square() 函数：计算每位平方数的和

slow：调用一次上述函数

fast：调用两次上述函数

代码实现：

 int Num_Square(int n){int sum = 0;while(n){sum += pow(n%10,2);n /= 10;}return sum;}bool isHappy(int n) {int slow = n;int fast = Num_Square(n);while(slow != fast){slow = Num_Square(slow);fast = Num_Square((Num_Square(fast)));}if(slow == 1){return true;}else{return false;}}

4：装最多的水(双指针+单调性)

题目要求：

解题思路：

遇事不决，暴力思路，那显然是不可能的，因为会超时间复杂度。单纯使用前面的双指针算法似乎也不可行。

问：那这里该如何解决，才能优化时间复杂度呢？

答：这里不仅仅需要双指针，还需要结合单调性去考虑问题。

我们先定义两个指针：

left：初始值为0，指向数组最左端。

right：初始值为 n-1，n为数组元素个数，指向数组最右端。

现在想想水的容积是怎么算的？

容积 = 两边最短的高度 × 长度（right - left）；

结合单调性，不难想到，如果此时 right--，left不变，那么任何数乘以 1 ，都会小于原来的容积(因为高度不变，长度减小)，因此我们只需记录目前的最大值，然后left++，这样就减少了遍历次数，提升了效率。

此时 left = 1，right = n -1，同样结合上述单调性来看，如果left++，right 不变，那么任何数乘以 7，都会小于原来数(同样是因为高度不变，长度减小)，因此这次我们需要将 right--，left不变，这样就减少了遍历次数，提升了效率。

总结：通过双指针+单调性去考虑这个问题

起始时：left = 0，right = n-1;

容积 = min(arr[left],arr[right]) × (right - left);

高度固定时，容积与长度为反比，记录此时容积大小，并改变较小的高度(left就++，right就--)

最终比较记录的容积值即可。

代码实现：

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

5：有效三角形个数(双指针+单调性)

题目要求：

解题思路：

通常我们通过判断三次两边之和小于第三边来确定三个数是否能够构成三角形。

问：怎么做？才能够减少判定次数，同时又能确定可以构成三角形？

答：用较小的两个边的和与最大的边进行比较，这样只需判断一次。

问：那如何找最大值呢？

答：遍历数组去找肯定是不可取的，那么就会想到，使用库函数的排序，这样最大值一定在数组末尾。

在有了上述的考虑后，本题同样是双指针+单调性去思考问题，无非就是条件不同。

以下列数组为例分析：

图一：

arr[left] + arr[right] < max 不构成三角形，那么比 arr[right] 小的数都不构成三角形，因此不用遍历，left++

图二：

arr[left] + arr[right] > max 构成三角形，那么此时只要比 arr[left] 大的数，都能够构成三角形，因此无需遍历，直接记录一共可以构成三角行的个数 n = right - left。记录完后，right--

图三：

此时，又回到了图一的情况，不多赘述，left++。

直至不满足 left < right ，此时需要更新 max，left 和 right 重新循环上述过程，知道 max = arr[2];

代码实现：

int triangleNumber(vector<int>& nums) {sort(nums.begin(),nums.end());size_t n = nums.size() -1;int total = 0;while(n >=2){int left = 0;int right = n-1;while(left < right){if(nums[left] + nums[right] <= nums[n]){left++;}else{total += right - left;right--;}}n--;}return total;}

6：和为 s 的两个数字(双指针+单调性)

题目要求：

解题思路：

几乎与5是一样的，只不过5中是与数组中的元素比，而这里是与给定的数比，因此更简单。

大致思路：

考虑双指针(left,right)，因为数组是有序数组，从单调性考虑。

若 arr[left] + arr[right] > target 说明太大了，right--

若 arr[left] + arr[right] < target 说明太小了，left++

代码实现：

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

7:三数之和

题目要求：

解题思路：

仍就是通过双指针+单调性的思路去解决这道问题，但区别在于，我们不能够输出重复的答案，因此这里还多了一个判重的过程。

如图定义来进行模拟运算：

当 arr[left] + arr[right] < arr[min] 时，left++;

当 arr[left] + arr[right] >arr[min] 时，right--;

当 arr[left] + arr[right] = arr[min] 时，left++;如图所示

此时需将答案保存到临时容器中，并让left++，right--,同时需要去重，即：

当 arr[left] == arr[left-1]时，left++；

当 arr[right] == arr[right+1]时，right--；

同时需要注意越界，即在循环过程中，left 始终小于 right；

当 left 大于 right时结束一轮循环时，此时 min++，也要去重，与left 与 right 的去重思路一致，同时注意越界，min 始终小于容器内数据个数。

代码实现：

vector<vector<int>> threeSum(vector<int>& nums) {int min = 0;vector<vector<int>> tmp;sort(nums.begin(),nums.end());//让数组变得有序方便使用单调性while(min < nums.size() && nums[min]<= 0){int left = min+1;int right = nums.size() - 1;while(left < right){int sum = nums[left] + nums[right];if(sum + nums[min] > 0){right--;}else if(sum + nums[min] < 0) {left++;}else{tmp.push_back({nums[min],nums[left++],nums[right--]});while(left < right && nums[left] == nums[left - 1]){left++;}while(left < right && nums[right] == nums[right + 1]){right--;}}}min++;while(min < nums.size() && nums[min] == nums[min-1]){min++;}}return tmp;}

8:四数之和

题目要求：

解题思路：

四数之和与三数之和的思路极其类似，无非就是多了一个需要固定的数，以及多一层循环，本质没有太大区别。

如图所示，固定 min 和 min1 去移动 left 和 right

当 arr[min] + arr[min1] + arr[left] + arr[right] < target时，left++

当 arr[min] + arr[min1] + arr[left] + arr[right] > target时，right--

当 arr[min] + arr[min1] + arr[left] + arr[right] = target时，

将当前 arr[min] ，arr[min1] ， arr[left] ， arr[right] 插入临时容器中

left++,right--，再判重，并注意越界

当最内层 left 和 right 循环结束时，min1++，并判重注意越界，开始下一轮循环

当 min1 等于倒数第三个下标时，第二层循环的首轮结束，min++，并判重，以此往复，直至循环结束。

代码实现：

vector<vector<int>> fourSum(vector<int>& nums, int target) {int min = 0;int n = nums.size()-1;vector<vector<int>> tmp;sort(nums.begin(),nums.end());while(min <= n-3){int min1 = min+1;while(min1 <= n-2){int left = min1+1;int right = nums.size() - 1;while(left < right){long sum = nums[left] + nums[right];long sum1 = nums[min] + nums[min1];if(sum + sum1 > target){right--;}else if(sum + sum1 < target) {left++;}else{tmp.push_back({nums[min],nums[min1],nums[left++],nums[right--]});while(left < right && nums[left] == nums[left - 1]){left++;}while(left < right && nums[right] == nums[right + 1]){right--;}}}min1++;while(min1 <= n-2 && nums[min1] == nums[min1-1]){min1++;}}min++;while(min <= n-3 && nums[min] == nums[min-1]){min++;}}return tmp;}