优选算法之双指针

1.移动零

1.1题目解析

1.2算法原理

• 这道题可以归为数组划分，数组分块这类题中，特点是分成两个不同的区域，利用双指针算法（利用数组下标来充当指针），定义两个指针cur，dest
• 两个指针的作用：cur 从左往右扫描数组，遍历数组；dest 已处理的区间内，非零元素的最后一个位置
• 三个区间：[0,dest]非0[dest+1,cur-1]0[cur,n-1]待处理
• 为什么第二个区间是cur-1，回到cur的定义上，cur是从左往右扫描数组，遍历这个数组的

• 如何做到？cur从前往后遍历的过程中，遇到0元素：cur++；遇到非0元素：交换元素swap(dest+1,cur);dest++;cur++;

1.3编写代码

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; } } } }

2.复写零

2.1题目解析

2.2算法原理

解法:双指针算法

先根据"异地操作",然后优化成双指针下的"就地"操作

1. 先找到最后一个"复写"的数;
2. "从后向前完成复写操作".

• 怎么找复写的数?

双指针算法

1. 先判断cur位置的值
2. 决定dest向后移动一步或两步
3. 判断一下dest是否已经到结束为止
4. cur++;

• 注意:cur和dest的执行顺序,dest先移动,再判断有没有出界,如果没有cur++;如果dest越界,直接跳出循环，cur也就不用移动。

• 处理边界情况? n-1 ->0 ;cur--;dest-=2;

2.3代码实现

class Solution { public void duplicateZeros(int[] arr) { int cur=0; int dest=-1; int n=arr.length; //1.找最后一个复写的数 while(cur<n){ if(arr[cur]!=0){ dest+=1; }else{ dest+=2; } if(dest>=n-1) break; cur++; } //2.处理边界情况 if(dest==n){ arr[n-1]=0; cur--; dest-=2; } //3.从后向前完成复写操作 while(cur>=0) { if(arr[cur]!=0) arr[dest--]=arr[cur--]; else{ arr[dest--]=0; arr[dest--]=0; cur--; } } } }

3.快乐数

3.1题目解析

3.2算法原理

解法：快慢双指针

1. 定义快慢指针
2. 慢指针每次向后移动一步，快指针每次向后移动两步
3. 判断相遇时候的值即可

注意：slow和fast不能一开始都定义为n,不然循环都进不去

3.3代码实现

class Solution { public int bitSum (int n){ //返回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=bitSum(n); while(slow!=fast){ slow=bitSum(slow); fast=bitSum(bitSum(fast)); } return slow==1; } }

4.盛水最多的容器

4.1题目描述

4.2算法原理

解法一：暴力枚举 O（n^2）超时

解法二：利用单调性，使用双指针来解决问题 O(n)

左右指针从两端出发 面积=较小高度*指针距离，每次只移动较小的数，过程中记录最大面积，为什么呢？因为面积受限于较小的数，如果移动较高的数，由于宽度变小了 ，但水的高度上限不变，面积不可能变大，只有移动较小的数，才有机会遇到面积最大

4.3代码实现

class Solution { public int maxArea(int[] height) { int left=0; int right=height.length-1; int ret=0; //记录结果 while(left<right){ int 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.有效三角形的个数

5.1题目解析

5.2算法原理

补充数学知识：给我们三个数，判断是否能够构成三角形，如果三角形三条边为a,b,c，a<=b<=c，满足a+b>c，构成三角形

优化：先对这个数组排序

解法一:暴力枚举 O(n^3)

//伪代码

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

for(int j=i+1;j<n;j++){

for(k=j+1;k<n;k++){

check(i,j,k);

解法二:利用单调性,使用双指针算法来解决问题 O(n^2)

1. 先固定最大的数
2. 在最大的数的左区间内,使用双指针算法,快速统计出符合要求的三元组的个数

5.3代码实现

class Solution { public int triangleNumber(int[] nums) { //1.排序 Arrays.sort(nums); int ret=0;// 结果 int n=nums.length; //2.固定最大的数 for(int i=n-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.和为s的两个数字

6.1题目解析

6.2算法原理

解法一:暴力枚举的策略 O(n^2)

//伪代码
for(int i=0;i<n;i++){
for(int j=i+1;j<n;j++){
check(nums[i]+nums[j]==t);

解法二:利用单调性,使用双指针算法解决问题

1. sum > t : right--
2. sum < t : left++
3. sum = t :返回结果

6.3代码实现

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

7.三数之和

7.1题目解析

7.2算法原理

解法一 : 排序+暴力枚举+利用set去重 O(n^3)

解法二 : 排序+双指针

1. 排序;
2. 固定一个数a; a<=0;
3. 在该数后面的区间内,利用"双指针算法"
4. 快速找到两个的和等于 -a即可.

处理细节问题:

1. 去重 找到一种结果之后,left 和right 指针要跳过重复元素 , 当使用完一次双指针短算法之后, i 也需要跳过重复元素注意 : 避免越界
2. 不漏 找到一种结果之后,不要"停",缩小区间,继续寻找

7.3代码实现

class Solution { public List<List<Integer>> threeSum(int[] nums) { List<List<Integer>> ret=new ArrayList<>();//结果 //1.排序 Arrays.sort(nums); //2.利用双指针解决问题 int n=nums.length; int i=0; //固定数a while(i<n){ if(nums[i]>0) break; int left=i+1; int right=n-1; int target=-nums[i]; while(left<right){ int sum=nums[left]+nums[right]; if(sum>target){ right--; }else if(sum<target){ left++; }else{ //找到一个符合条件的 ret.add(new ArrayList<Integer>(Arrays.asList(nums[i],nums[left],nums[right]))); left++;right--; //去重 left right while(left<right && nums[left]==nums[left-1]){ left++; } while(left<right && nums[right]==nums[right+1]){ right--; } } } i++; //去重 i while(i<n && nums[i]==nums[i-1]){ i++; } } return ret; } }

8.四数之和

8.1题目解析

8.2算法原理

解法一:排序+暴力枚举+利用set去重

解法二: 排序+双指针

1. 依次固定一个数a;
2. 在 a 后面的区间内,利用"三数之和"找到这三个数,使得这三个数的和等于target - a即可

三数之和:

1. 依次固定一个数 b ;
2. 在 b 后面的区间内,利用双指针找到两个数,使这两个数的和等于target - a - b 即可.

处理细节问题:

1. 不重
2. 不漏

8.3代码实现

class Solution { public List<List<Integer>> fourSum(int[] nums, int target) { List<List<Integer>> ret=new ArrayList<>(); //1.排序 Arrays.sort(nums); //利用双指针解决问题 int n=nums.length; for(int i=0;i<n;){ //固定数a for(int j=i+1;j<n;){ //固定数b //三数之和 int left=j+1; int right=n-1; long aim=(long)target-nums[i]-nums[j]; while(left<right){ int sum=nums[left]+nums[right]; if(sum>aim){ right--; }else if(sum<aim){ left++; }else{ ret.add(Arrays.asList(nums[i],nums[j],nums[left++],nums[right--])); //去重 left right while(left < right && nums[left]==nums[left-1]){ left++; } while(left < right && nums[right]==nums[right+1]){ right--; } } } j++; //去重 j while(j<n && nums[j]==nums[j-1]) j++; } i++; //去重 i while(i<n && nums[i]==nums[i-1]) i++; } return ret; } }