算法专题一双指针
算法专题一：双指针
1.移动零
题目链接：
我们可以定义一个dest，一个cur，dest表示数组中不为零的数的最后一位，cur用来遍历数组
class Solution {
public void moveZeroes(int[] nums) {
for(int cur=0,dest=-1;cur= n - 1){
break;
}
cur++;
}
if(dest==n){
arr[n-1]=0;
dest-=2;
cur–;
}
while(cur>=0){
if(arr[cur]!=0){
arr[dest–]=arr[cur–];
}else{
arr[dest–]=0;
arr[dest–]=0;
cur–;
}
}
}
}
3.快乐数
题目链接：
所以我们的算法原理：可以定义一个快指针，一个慢指针，快指针每次走两步，慢指针每次走一步，直至两个指针相遇，如果相遇时的数为1，则是快乐数，如果不是1，就不是快乐数。
代码如下：
class Solution {
public int sum(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=sum(n);
while(slow!=fast){
slow=sum(slow);
fast=sum(sum(fast));
}
return slow==1;
}
}
4.盛最多水的容器
题目链接：[11 盛最多水的容器 - 力扣（LeetCode）](
with-most-water/description/ “11. 盛最多水的容器 - 力扣（LeetCode）”)
大家看到这个题目一定会想到这道题的暴力解法，套两层for循环，进行暴力枚举，但是这种解法会超时。O（n2）
我们就要需要找到其中的规律
比如这种情况：
我们从中取出一小部分进行讲解
体积无非就是长 * 宽
我们通过左右的比较，发现6比3大，我们可以将3的位置往前移动一位。
这样移动的思想就是，我们如果将6往前移动一位，无非就是三种情况
- 宽度减小，高度不变
- 宽度减小，高度也减小
- 宽度减小，高度不变 无论我们怎么样移动体积都会减小，所以我们每次将两边较小的进行移动。 代码如下： class Solution { public int maxArea(int[] height) { int left=0; int right=height.length-1; int result=0; while(left < right){ int v=Math.min(height[left],height[right]) * (right-left); result=Math.max(v,result); if(height[left]=2;i–){ int left=0; int right=i-1; while(lefttarget){ right–; }else{ return new int[]{price[left],price[right]}; } } return new int[]{0}; } }
7.三数之和
题目链接：
小优化：
class Solution {
public List> threeSum(int[] nums) {
Arrays.sort(nums);
List> ret =new ArrayList<>();
int n=nums.length;
for(int i=0;i0){
break;
}
while(lefttarget){
right–;
}else if(sum(Arrays.asList(nums[i],nums[left],nums[right])));
left++;
right–;
while(left> fourSum(int[] nums, int target) {
List> ret=new ArrayList<>();
Arrays.sort(nums);
int n=nums.length;
for(int i=0;iaim){
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++;
while(j<n && nums[j]==nums[j-1]){
j++;
}
}
i++;
while(i<n && nums[i]==nums[i-1]){
i++;
}
}
return ret;
}
}
希望能对大家有所帮助！！！
