算法第一弹-----双指针

目录

1.移动零

2.复写零

3.快乐数

4.盛水最多的容器

5.有效三角形的个数

6.查找总价值为目标值的两个商品

7.三数之和

8.四数之和

---

双指针通常是指在解决问题时，同时使用两个指针（变量，常用来指向数组、链表等数据结构中的元素位置），通过对这两个指针的移动和操作来高效地处理数据、查找元素、遍历结构等，从而达到降低时间复杂度、优化算法的目的。

 

根据指针移动的方向和规则不同，双指针可以大致分为以下两类：

• 同向双指针：
  两个指针起始位置可能相同或者不同，但它们朝着同一个方向移动，比如都从数组头部向尾部移动，常用于处理需要连续遍历部分区间、查找满足特定条件的子区间等问题。常使用快慢指针

• 对撞双指针：
  两个指针分别从数据结构（常见的如数组、字符串等）的两端开始，然后相向而行，朝着彼此靠近的方向移动，这种方式常常应用在判断回文、两数之和类问题（当数据有序时）等场景中。

1.移动零

283. 移动零 - 力扣（LeetCode）

---

题目描述：

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

请注意 ，必须在不复制数组的情况下原地对数组进行操作。

---

示例 1:

输入: nums = [0,1,0,3,12]
输出: [1,3,12,0,0]

示例 2:

输入: nums = [0]
输出: [0]

---

解法：（使用快排的思想，将数组划分区间）

算法思路：

1.我们使用两个指针（left，right），规定left左边区域为非零的数字，right去向后扫描，遇到非零的数字，先让left++，然后再让left和right所指下标的数字进行交换，这样就保证了当right扫描完整个数组时，left左边（包括left）的区域全是非零的数字

2.left初始化为-1，是因为left指向的是非零元素的最后一个位置，刚开始我们并不知道最后一个非零元素在哪，所以初始化为-1，right是用来扫描的，所以初始化为0

---

JAVA算法代码：

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

2.复写零

1089. 复写零 - 力扣（LeetCode）

---

题目描述：

给你一个长度固定的整数数组 arr ，请你将该数组中出现的每个零都复写一遍，并将其余的元素向右平移。

注意：请不要在超过该数组长度的位置写入元素。请对输入的数组 就地 进行上述修改，不要从函数返回任何东西。

---

示例 1：

输入：arr = [1,0,2,3,0,4,5,0]
输出：[1,0,0,2,3,0,0,4]
解释：调用函数后，输入的数组将被修改为：[1,0,0,2,3,0,0,4]

示例 2：

输入：arr = [1,2,3]
输出：[1,2,3]
解释：调用函数后，输入的数组将被修改为：[1,2,3]

---

解法：分三步，第一步找到最后一个要复写的元素，第二步处理一下边界情况，第三步从后往前遍历数组，依次填写出复写后的结果

算法思路

1.使用cur去遍历数组，dest去确定最后一个复写元素的位置，cur初始化为0，dest初始化为-1

2.使用cur遍历数组，当cur所指元素不为0时，dest++，当cur所指元素为0时dest+=2；并且每次循环判断dest是否到达数组的最后一个位置或超出数组，如果dest>=arr.length-1,那么就找到了最后一个要复写的元素，直接break跳出循环

3.当最后一个要复写的元素是0时，且dest处在数组的倒数第二个位置，这时，dest就会向后走两格，就会造成数组越界，其他情况均不会造成数组越界

4.面对数组越界这种情况，我们在从后往前填写复写结果时，需要做一下边界处理，当dest为n时，也就是越界了，因为此时一定是最后一个复写元素是0，我们需要将数组的最后一个元素设为0，然后dest-=2，cur--

5.从后往前复写，当cur所指元素为0时，dest位置设置为0，dest-1位置也设置为0，dest-=2，cur--

当cur所指元素不为0时，将dest位置设置为cur所指元素，dest--，cur--，当cur<0时，也就是cur从后往前遍历完毕，复写操作也就完毕了

---

JAVA算法代码：

class Solution {public void duplicateZeros(int[] arr) {int dest=-1;int cur=0;int n=arr.length;
//找到要的结果的最后一个位置while(dest<n){
if(arr[cur]==0)dest+=2;
else dest++;
if(dest>=n-1)break;
cur++;}
//处理边界情况if(dest==n){arr[n-1]=0;cur--;dest-=2;}
//从后往前写
while(cur>=0){
if(arr[cur]==0){arr[dest--]=0;arr[dest--]=0;
}else{arr[dest--]=arr[cur];
}
cur--;
}}
}

3.快乐数

202. 快乐数 - 力扣（LeetCode）

---

题目描述：

编写一个算法来判断一个数 n 是不是快乐数。

「快乐数」 定义为：

• 对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
• 然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。
• 如果这个过程 结果为 1，那么这个数就是快乐数。

如果 n 是 快乐数 就返回 true ；不是，则返回 false

---

示例 1：

输入：n = 19
输出：true
解释：
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1

示例 2：

输入：n = 2
输出：false

---

解法：快慢指针，判断相遇时的值是否为1

算法思路

1.题目中给出的数据范围是1 <= n <= 2的31次方 - 1，2的31次方是一个10位数的数字，我们以9999999999的平方和来算，也就是810，那么在这个数据范围内的所有数据的平方和也就在1~810这个范围

2.根据鸽巢原理，当我们计算到第811个平方和时，就必然会陷入的一个循环

3.在这个循环里面，通过快慢指针，找到快慢指针相遇时的值，判断是否为1，如果为1，那么这个数就是快乐数，如果不为1，那么这个数就不是快乐数

4.快指针每次计算两次平方和，慢指针每次计算一次平方和；当快指针与慢指针相遇时，但相遇时的值不为1，这个数一定不是快乐数，这是因为快指针往后走的过程中，如果他有一次的平方和为1，那么他后面所有的平方和一定就都为1，陷入了一个1的循环，当快慢指针相遇时的结果不为1，说明快指针在走的过程中没有一次的平方和是1，就可以判定他必然不是快乐数

---

JAVA算法代码：

class Solution {
//计算平方和
public int quaSum(int n){
int sum=0;
while(n!=0){
int x=n%10;
sum+=x*x;
n/=10;
}
return sum;
}public boolean isHappy(int n) {int fast=quaSum(n);int slow=n;
while(slow!=fast){
fast=quaSum(quaSum(fast));
slow=quaSum(slow);
}
return slow==1;}
}

4.盛水最多的容器

11. 盛最多水的容器 - 力扣（LeetCode）

---

题目描述

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。

找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

返回容器可以储存的最大水量。

说明：你不能倾斜容器。

---

示例 1：

输入：[1,8,6,2,5,4,8,3,7]
输出：49 
解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。

示例 2：

输入：height = [1,1]
输出：1

---

解法：（对撞指针）

算法思路

1.使用两个指针（left，right）分别指向这个容器的两端，计算容器的大小，通过移动指针，找到最大的容器

2.当移动指针宽度是一定减小的，此时如果再移动高的一边（也就是较高高度一边的指针），那么容器的大小一定是减小的，容器的大小是由宽度和较小一边的高度决定的，移动指针时，只能移动较矮一边的指针

3.新的容器大小和之前的最大的容器大小比较，如果比之前大，就将之前的最大容器修改为新的容器大小，否则继续计算下一个容器的大小，直到两个指针相遇，返回最大的容器大小

---

JAVA算法代码

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

5.有效三角形的个数

611. 有效三角形的个数 - 力扣（LeetCode）

---

题目描述

给定一个包含非负整数的数组 nums ，返回其中可以组成三角形三条边的三元组个数。

---

示例 1:

输入: nums = [2,2,3,4]
输出: 3
解释:有效的组合是: 
2,3,4 (使用第一个 2)
2,3,4 (使用第二个 2)
2,2,3

示例 2:

输入: nums = [4,2,3,4]
输出: 4

---

解法：排序，对撞指针

算法思路

1.对数组进行排序，当较小的两边和大于第三边时，那么三边中中间大的数与最小边中间的数均可与中间大的数和最大边构成三角形

2.通过循环，每次固定最大边，left表示最小边，right表示中间的边

3.最大边从数组长度-1开始--（用i表示），left在每次循环里初始化为0，right在每次循环里初始化为i-1;ret记录符合条件的个数。

4.当nums[left]+nums[right]>nums[i]时，说明用left到right之间的数来充当left，nums[left]+nums[right]的结果都是大于nums[i]，此时ret+=right-left，将right像左移动，再继续判断下一个区间

5.当nums[left]+nums[right]<nums[i]时，不符合条件，我们需要将left向右移动，使nums[left]+nums[right]的值更大，当left与right相遇时，说明i固定的值的所有可能结果找完了

---

JAVA算法代码：

class Solution {public int triangleNumber(int[] nums) {Arrays.sort(nums);int ret=0;for(int i=nums.length-1;i>=2;i--){
int left=0;
int right=i-1;
while(left<right){
if(nums[left]+nums[right]>nums[i]){ret+=right-left;right--;
}else
left++;
}}return ret;}
}

6.查找总价值为目标值的两个商品

LCR 179. 查找总价格为目标值的两个商品 - 力扣（LeetCode）

---

题目描述

购物车内的商品价格按照升序记录于数组 price。请在购物车中找到两个商品的价格总和刚好是 target。若存在多种情况，返回任一结果即可。

---

示例 1：

输入：price = [3, 9, 12, 15], target = 18
输出：[3,15] 或者 [15,3]

示例 2：

输入：price = [8, 21, 27, 34, 52, 66], target = 61
输出：[27,34] 或者 [34,27]

---

解法：对撞指针

算法思路

1.定义left和right两个指针

2.left初始化为1，right初始化为price.length-1

3.计算price[left]+price[right]的和与target做比较，大于righr--，小于left++，等于返回含有这两个元素的数组

---

JAVA算法代码

class Solution {public int[] twoSum(int[] price, int target) {int left=0;int right=price.length-1;while(left<right){
if(price[left]+price[right]>target)right--;
else if(price[left]+price[right]<target)left++;
elsereturn new int[] {price[left], price[right]};}return new int[]{0};}
}

7.三数之和

15. 三数之和 - 力扣（LeetCode）

---

题目描述

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。

注意：答案中不可以包含重复的三元组。

---

示例 1：

输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
解释：
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意，输出的顺序和三元组的顺序并不重要。

示例 2：

输入：nums = [0,1,1]
输出：[]
解释：唯一可能的三元组和不为 0 。

示例 3：

输入：nums = [0,0,0]
输出：[[0,0,0]]
解释：唯一可能的三元组和为 0 。

---

解法：固定一个数，取相反值，对撞指针

算法思路

1.对数组进行排序

2.遍历数组，每次遍历，固定当前这个数，计算他的相反值，定义两个指针（left，right），left初始化为i+1，right初始化为nums.length-1，使用对撞指针，在i后面的区域内搜寻nums[left]+nums[right]==target的值，找到了就将i，left，right所指的值添加到链表里面

3.如果i所指的值是大于0的，那么就不用继续搜寻了，因为-nums[i]为负数，后面的nums[left]+nums[right]始终为正

4.去重操作，当我们找到一组数后，需要对left，right的值进行去重操作，当固定完一个数后，也需要对这个固定的数进行去重操作

---

JAVA算法代码

class Solution {public List<List<Integer>> threeSum(int[] nums) {List<List<Integer>>ret=new ArrayList<>();Arrays.sort(nums);
int n=nums.length;for(int i=0;i<n;){
int target=-nums[i];
int left=i+1;
int right=n-1;
if(nums[i]>0)break;
while(left<right){
if((nums[left]+nums[right])==target){ret.add(new ArrayList<Integer>(Arrays.asList(nums[i],nums[left], nums[right])));left++;right--;while(left<right&&nums[left-1]==nums[left])left++;
while(left<right&&nums[right+1]==nums[right])right--;
}else if(nums[left]+nums[right]<target)left++;
else right--;
}
i++;
while(i<n&&nums[i-1]==nums[i])i++;}
return ret;}
}

8.四数之和

18. 四数之和 - 力扣（LeetCode）

---

题目描述

给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：

• 0 <= a, b, c, d < n
• a、b、c 和 d 互不相同
• nums[a] + nums[b] + nums[c] + nums[d] == target

你可以按 任意顺序 返回答案 。

---

示例 1：

输入：nums = [1,0,-1,0,-2,2], target = 0
输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

示例 2：

输入：nums = [2,2,2,2,2], target = 8
输出：[[2,2,2,2]]

---

解法：基于三数之和

算法思路

1.对数组进行排序

2.从0开始遍历数组，固定第一个数，从固定i+1位置数，遍历第二个数，用target减去第一个和第二个数得到aim，aim可能会超出int的范围，用long类型处理一下

3.用对撞指针left和right搜寻两数之和为aim的可能结果，每次找到，对left和right进行去重处理，第一个数和第二个数在自己循环一次过后也需要进行去重处理

---

JAVA算法代码

class Solution {public List<List<Integer>> fourSum(int[] nums, int target) {List<List<Integer>>ret=new ArrayList<>();Arrays.sort(nums);int n=nums.length;for(int i=0;i<n-3;){
for(int j=i+1;j<n-2;){
int left=j+1;
int right=n-1;
long aim=(long)target-nums[j]-nums[i];
while(left<right){long sum=nums[left]+nums[right];
if(sum<aim)left++;
else if(sum>aim)right--;
else{
ret.add(new ArrayList<>(Arrays.asList(nums[i],nums[j],nums[left],nums[right])));
left++;
right--;
while(left<right&&nums[left-1]==nums[left])left++;
while(left<right&&nums[right+1]==nums[right])right--;
}
}
j++;
while(j<n-2&&nums[j-1]==nums[j])j++;
}
i++;
while(i<n-3&&nums[i-1]==nums[i])i++;}return ret;}
}