算法【Java】—— 双指针算法

CSDN 2024-08-20 12:35:04 阅读 72

双指针算法

常见的双指针有对撞指针,快慢指针以及前后指针(这个前后指针是指两个指针都是从从一个方向出发,去往另一个方法,也可以认为是小学学习过的两车并行,我也会叫做同向指针),在前后指针这里还有一个经典的算法叫做滑动窗口,滑动窗口会在下一篇算法文章中提到

对撞指针可以叫做左右指针,就是一个指针在最左端,另一个指针在最右端,然后两个指针开始向中间逼近。

快慢指针:相信大家在链表的时候就已经学到过,就是一个指针每次走一步(这就是慢指针),另一个指针每次走两步(这是快指针)。一般快慢指针是用来处理处理环形链表或数组。

前后指针:在不涉及到滑动窗口的使用的时候,我们一般会用于数组的分区

如果大家学过排序,想必对双指针应该十分了解,正好在学习双指针算法的时候,可以回顾一下排序内容。

题目实战

下面题目讨论的时间复杂度没有进行化简,目的是让大家更好地感受算法对性能的优化。

移动零

https://leetcode.cn/problems/move-zeroes/description/

在这里插入图片描述

解法:前后指针

题目要求我们将数组前面的零移动到后面,将非零的元素按照原本的相对位置存放到数组的前面。

这时候这个数组显而易见地被分成了两个部分,一个是非零区域,一个是零区域

我们可以使用前后指针法,第一个指针从下标0开始遍历数组,第二个指针初始值设置为-1,当第一个指针遇到非零元素时,第二个指针向后移动一步,然后交换两个指针所对应的数组的元素,否则第二个指针原地不动。

在这里插入图片描述

通过前后指针,我们可以将数组分成上述的区域,这就是为什么前后指针一般用于数组的分区。

<code>class Solution { -- -->

public void moveZeroes(int[] nums) {

int len = nums.length;

int j = -1;

for(int i = 0; i < len; i++) {

if(nums[i] != 0) {

j++;

int tmp = nums[i];

nums[i] = nums[j];

nums[j] = tmp;

}

}

}

}

如果可以使用额外的空间的话,还是使用两个指针,一个指针指向一个数组,时间复杂度为O(2N),空间复杂度为O(N),但是直接使用双指针算法,时间复杂度O(2N),空间复杂度为O(1)

快乐数

https://leetcode.cn/problems/happy-number/

在这里插入图片描述

解法:快慢指针

在快乐数的循环中,我们知道循环最后的结果要么是无限循环,要么是 1,那无限循环是为什么?

以 n = 2 为例:2 ^ 2 = 4,4 ^ 2 = 16,1 ^ 2 + 6 ^ 2 = 37,3 ^ 2 + 7 ^ 2 = 58,5 ^ 2 + 8 ^ 2 = 89,8 ^ 2 + 9 ^ 2 = 145, 1 ^ 2 + 4 ^ 2 + 5 ^ 2 = 42,4 ^ 2 + 2 ^ 2 = 20,2 ^ 2 + 0 = 2,最后你会发现这个数它又回去了,也就是意味着这个循环形成了一个环

最后循环的结果还有一种可能就是出现1,如果出现 1 的时候,我们不停止循环的话,那么这个循环将会一直得到1,这也是一个环。

相信大家到这里想到了使用快慢指针,当两个指针相遇时,如果指针对应的是1 的话,那么就是快乐数,否则就不是快乐数。

<code>class Solution { -- -->

public boolean isHappy(int n) {

int slow = n;

int fast = sum(sum(n));

while(slow != fast) {

slow = sum(slow);

fast = sum(sum(fast));

}

if(slow == 1) {

return true;

} else {

return false;

}

}

private int sum(int n) {

int sum = 0;

while(n != 0) {

sum += (n % 10) * (n % 10);

n /= 10;

}

return sum;

}

}

盛最多水的容器

https://leetcode.cn/problems/container-with-most-water/description/

在这里插入图片描述

解法:对撞指针

分析题意:数组的每一个元素是该下标的高,而容器的底长为两个下标之间的差值,题目要求我们找到容器的最大值,这个数值等于 高 x 底长

我们使用对撞指针,一个在最左端,一个在最右端,然后两个指针开始向中间遍历,首先由于两个指针是向中间靠拢,所以对应的宽度就会减少,指针移动的目的是为了获取容器的最大值,所以,我们现在要思考指针如何移动?

因为容器的高度是由最小的高度决定的,所以这时候,我们可以从两个指针获取到最小的元素,我们让对应最小的高度的指针向中间移动,看看能不能找到更大的高度,以此来进行遍历,然后通过 Math.max 这个函数就可以获取到最大值。

<code>class Solution { -- -->

public int maxArea(int[] height) {

int left = 0;

int right = height.length - 1;

int maxV = Math.min(height[left],height[right]) * (right - left);

while(left < right) {

int index = (height[left] > height[right] ? right : left);

if(index == left) {

left++;

} else {

right--;

}

int tmp = Math.min(height[left],height[right]) * (right - left);

maxV = Math.max(maxV,tmp);

}

return maxV;

}

}

这道题的对撞指针算法的时间复杂度为O(N) ,性能十分地好

两数之和

https://leetcode.cn/problems/he-wei-sde-liang-ge-shu-zi-lcof/

在这里插入图片描述

解法:排序 + 双指针

由于我们只要返回两个数(两数之和为 target 即可)。如果我们直接使用两个指针的话,就是使用暴力枚举,使用了两层循环,实践复杂度为O(N^2),但是这里是算法篇目,我们应该尽量优化我们的算法,将算法的效率提高。

如果数组本身就是有序的话,我们再这个基础上使用双指针就会好写很多,因为就三种情况,要么两数之和小于taregt ,两数之和如果等于 tareget 的话,直接返回即可,如果两个数大于 target 。

也就是我们要处理指针的移动就是大于和小于的情况,如果是大于的话,我们可以将指针左移减小两数之和,如果是小于的话,可以将指针右移扩大两数之和,那这就意味着我们要使用的是对撞指针。

<code>class Solution { -- -->

public int[] twoSum(int[] price, int target) {

Arrays.sort(price);

int left = 0;

int right = price.length - 1;

while(left < right) {

if(price[left] + price[right] == target) {

break;

} else if(price[left] + price[right] > target) {

right--;

} else {

left++;

}

}

int[] ans = { price[left],price[right]};

return ans;

}

}

时间复杂度分析,使用Arrays.sort ,这个底层是快速排序,时间复杂度为O(N * logN),对撞指针时间复杂度为 O(N), 整体时间复杂度为 O(N + N * logN),比暴力枚举好多了。

三数之和

https://leetcode.cn/problems/3sum/

在这里插入图片描述

解法:双指针

在做这道题目的时候,我们一开始想到的就是直接暴力求解,使用三个循环,时间复杂度为 O(N ^ 3) ,作为一个算法题,我们需要优化它的性能,我们可以使用双指针来代替两个循环,这样最多只需要遍历 2N 个元素,加上一个循环,时间复杂度就可以变为 O(N ^ 2)

我们可以借助两数之和这道题目的算法思路,通过对撞指针找到 两数之和为 taregt ,而target 可以由 0 - 第三个数字获得,使用这个思路的时候,需要先对数组排好序。

这里有一个方法 能将一串数字转化为 链表 —— Arrays.asList(…),这样就不用这么麻烦添加元素到链表上了

这里要避免重复的三元组的出现,再取完三元组后,双指针各自向中间靠拢一步,然后进行去重操作,避免和上回的元素相同。

在每次执行完双指针算法的时候,可以再对 最外层循环的变量先 ++ ,再去重,因为这个元素的三元组已经找过了。

为什么去重之后,三元组就不会重复?

因为数组是有序的,双指针是向中间靠拢的,左指针所对应的数值一定的大于上回的数值,右指针对应的数值一定的小于上回的数值,并且左指针一定小于右指针,所以右指针不可能去到左指针上回的数值,这就保证有一个数字是一定不重复的,也就保证三元组的不重复性

经过双指针的优化,时间复杂度为O(N^2 + N * logN)

<code>class Solution { -- -->

public List<List<Integer>> threeSum(int[] nums) {

Arrays.sort(nums);

List<List<Integer>> list = new ArrayList<>();

int len = nums.length;

for(int i = 0; i < len - 2;) {

int target = 0 - nums[i];

for(int left = i + 1, right = len - 1; left < right;) {

if(nums[left] + nums[right] == target) {

List<Integer> l = new ArrayList<>(Arrays.asList(nums[i],nums[left],nums[right]));

list.add(l);

left++;

right--;

while(left < right && nums[right+1] == nums[right]) {

right--;

}

while(left < right && nums[left-1] == nums[left]) {

left++;

}

} else if (nums[left] + nums[right] > target) {

right--;

} else {

left++;

}

}

//去重

i++;

while(i < len && nums[i-1] == nums[i]) {

i++;

}

}

return list;

}

}



声明

本文内容仅代表作者观点,或转载于其他网站,本站不以此文作为商业用途
如有涉及侵权,请联系本站进行删除
转载本站原创文章,请注明来源及作者。