图解 LeetCode 算法汇总——双指针

技术分享 2年前 (2023-09-19) 0 999+

双指针算法是一种比较常用于搜索链表或数组相关的问题，很多算法的基本的解题思路就是使用暴力搜索法。而双指针是对暴力搜索的一种优化，通过双指针可以减少数据的遍历次数。通常双指针是有两个指针，叫做 light 左指针和 right 右指针，或者叫做快指针和慢指针。

作为左右指针的话，一般是在数组的或者链表的头尾两侧，从两遍往中间收缩，获取到符合条件的答案。
作为快慢指针的话，主要应用于解决链表问题。通常快指针移动的比慢指针移动的快，这种方法可以用来检测链表中是否有环、寻找链表的中间结点。

LeetCode 题解

11.盛最多水的容器

题目描述

解题思路

这题可以暴力破解法，双循环遍历出来，查出所有存在的情况，但是时间复杂是O(N²)，实现简单，但是比较耗时。而且本题也无需遍历所有的情况，分析一下解题思路：

本题求解的是最大的盛水面积，盛水面积是由宽和高组成，也就是找到横坐标的长度 * 两条竖线中更端的线的乘积。

最开始时候，左右指针分别指向数组的左右两端，获取到容量 min(1,7) * 8。

然后两遍指针往中间收缩，需要往中间移动一个指针，重点是需要移动哪一个？往中间收缩，宽度一定是变短，而高度是由两条竖线中的最短的一条决定。移动更大竖线的指针，面积肯定会减少，因为宽度和高度都在减少，所以需要移动竖线更小的指针，面积才可能增加。上面移动左边的竖线。面积由原来的 min(1,7) * 8 = 8 到 min （8,7） * 7 = 49,面积增多了。

使用 max 变量记录当前最大的面积，和每次搜索的面积做对比，获取到最大值。代码如下所示：

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

15.三数之和

题目描述

解题思路 for + 双指针

无论是两数之和或者三数之和都可以使用到双指针，但是双指针只有两个指针无法同时记录三个数，所以就需要使用一个 for 循环，for 每次遍历记录一个值，再使用双指针记录左右两个值。

为了减少遍历的次数，需要对数组做一个排序。然后 for 循环定位到第一个元素，左右两个指针的目标值就是 target - for 循环定位元素。左右指针相加得到总和 sum。

如果sum < target,左指针往右移动。
如果sum > target，右指针往左移动。
如果sum = target，符合条件，返回值。

然后定位到第二个元素，继续使用双指针收缩遍历。

代码如下：

class Solution {     public List<List<Integer>> threeSum(int[] nums) {         List<List<Integer>> lists = new ArrayList<>();         Arrays.sort(nums); 	//for循环 + 双指针 	for (int i = 0; i < nums.length; i++) {             if (i > 0 && nums[i] == nums[i - 1]) {                 continue;             } 	    int target = -nums[i]; 	    int left = i +1,right = nums.length - 1;             while (left < right) { 		int sum = nums[left] + nums[right]; 		if (sum == target) { 		    List<Integer> list = new ArrayList<>(); 	            list.add(nums[i]); 		    list.add(nums[left]); 		    list.add(nums[right]); 		    lists.add(list); 		    break; 		} else if (sum < target) { 		    left++; 		} else { 		    right--; 		} 	} 	} 	return lists;     } }

142. 环形链表 II

题目描述

解决方案

这道题在链表那篇文章也有，求解使用了 hash 表，遍历链表，存储在 hash 表中。如果有相同的数据，说明链表是有环了。本题采用快慢指针的办法。

起始的时候，快慢指针都在首节点。

慢指针一次走一步，快指针一次走两步，移动第一次之后。

fast 指针走过链表末端，说明链表无环，此时直接返回 null。如果两个指针遇上，说明链表有环，当两个指针第一次相遇时，fast 走的步数是 slow 的两倍。

从相遇点到入环点的距离加上 n−1 圈的环长，恰好等于从链表头部到入环点的距离。当 slow 和 fast 相遇时，可以在使用一个额外的指针 ptr，开始指向链表头部，随后它和 slow 每次往后移动，最后他们会在入环结点相遇，此时就能获取到入环结点。

public class Solution {     public ListNode detectCycle(ListNode head) {         if (head == null) {             return null;         }         ListNode slow = head, fast = head;         while (fast != null) {             slow = slow.next;             if (fast.next != null) {                 fast = fast.next.next;             } else {                 return null;             }             if (fast == slow) {                 ListNode ptr = head;                 while (ptr != slow) {                     ptr = ptr.next;                     slow = slow.next;                 }                 return ptr;             }         }         return null;     } }