当前位置：首页 > news >正文

走进算法大门---双指针问题（一）

news 2024/11/13 3:44:26

一.双指针算法介绍

概念：双指针是指在遍历数据结构（如数组、链表等）时使用两个指针，通过特定的移动规则来解决问题。这两个指针可以同向移动，也可以相向移动。

同向双指针：常用于解决需要两个位置信息的问题。例如，在一个有序数组中查找两个数的和等于目标值的情况。一个指针从数组头部开始，另一个指针从当前指针的后面开始，通过不断调整指针位置来找到符合条件的数对。
相向双指针：典型应用是在排序数组中查找满足某种条件的子数组。比如，在一个递增的数组中，一个指针从数组开头，一个指针从数组末尾，根据两个指针所指元素的和、差等关系，向中间移动指针，直到满足特定条件。
优势：双指针算法可以降低时间复杂度，将原本需要嵌套循环的问题简化为单循环或更高效的遍历方式。例如，在某些情况下，可以将时间复杂度从n^2 降低到n 。

二.移动0

题目链接
在这里插入图片描述

class Solution {public void moveZeroes(int[] nums) {for(int cur = 0,dest = -1;cur<nums.length;cur++){if(nums[cur]!=0){dest++;int tmp = nums[cur];nums[cur]=nums[dest];nums[dest] =tmp;}}}
}

在这里插入图片描述

解题思路：主要把数组分为3个区间，已经处理过的非0区间，0元素区间和未处理的区间。

把数组分为3部分：

[0,dest] :处理过的非0元素
[dest+1,cur-1] 处理过的0元素
[cur,arry,length-1] 未被处理的元素

在这里插入图片描述

初始化时让cur 指向0元素位置，dest指向-1。刚开始所有元素都未处理，按照划分区间，未被处理的元素区间为【0，dest】，所以dest不能等于0，等于0说明第一个元素已经被处理过，边界不好区分，因此让dest=-1。
在这里插入图片描述

当cur的值等于0时，cur++;cur的值不等于0，让dest先走一步接着dest和cur 对应元素的值互相交换，每次都能保证数组的3个范围的划分。
在这里插入图片描述

在代码执行中，非零元素会依次覆盖零元素的位置，最终达到将所有零移动到数组末尾的目的。此方法的时间复杂度为 O(n)，空间复杂度为 O(1)，即为原地操作，不占用额外空间。如果暴力求解时间复杂度n方，双指针确实比暴力求解时间复杂度低。

三.快乐数

快乐数
在这里插入图片描述

class Solution {public int Num(int n) {int sum = 0;while (n!= 0) {int t = n % 10;sum += t * t;n /= 10;}return sum;}public boolean isHappy(int n) {int slow = n;int fast = Num(n);while (fast!= slow) {slow = Num(slow);fast = Num(Num(fast));}return slow == 1;}
}

解法：前面学习链表的时候我们学过判断链表是否带环，让快指针一次走2步，慢指针一次走一步，如果存在环它们总能相遇。

以19为例是该树快乐数，通过对19的运算结果确实是1，说明是快乐数。
在这里插入图片描述

以2为例判断不是快乐数。4和20形成了一个环，说明不是快乐数。
在这里插入图片描述
把这个环想象成链表带环，让快指针在环里面一次走2步，慢指针一次走一步总会在环里面的某个位置相遇，相遇后跳出循环判断相遇点的值是否为1，如果是1说明是快乐数，不是1说明不是。

关于是否会陷入死循环
在这个算法中，实际上是利用了快慢指针的思想。对于一个正整数，如果它不是快乐数，那么在不断计算各位数字平方和的过程中，最终会陷入一个循环。
由于数字的范围是有限的（对于给定的正整数，经过有限次的数字平方和计算后，得到的结果一定在一个有限的范围内）。
假设存在一个非快乐数，在计算过程中会进入一个循环，那么快慢指针一定会在这个循环中相遇。因为快指针每次移动两步，慢指针每次移动一步，在一个有限的循环中，快指针必然会追上慢指针。
如果这个数是快乐数，那么最终会得到1，此时快慢指针也会相等（因为最终都会到达1这个结果）。

四.盛最多容器的水

盛最多容器的水
在这里插入图片描述

class Solution {public int maxArea(int[] height) {int left = 0;int right = height.length - 1;int v = 0;while (left < right) {int min = Math.min(height[left], height[right]);v = Math.max(v, min*(right - left));if (height[right] > height[left]) {left++;} else {right--;}}return v;}
}