算法专题——双指针
目录
前言
1、移动0
2、复写零
3、快乐数
4、盛最多水的容器
5、有效三⻆形的个数
6、和为s的两个数字
7、三数之和
8、四数之和
前言
本文主要介绍一些用到双指针的常见算法题。
1、移动0
链接：https://leetcode.cn/problems/move-zeroes/description/
本题为数组分隔、数组分块问题，常见解法是使用双指针。
定义两个指针分别为cur和dest，将该数组划分为三个部分。使用cur遍历数组，cur前代表处理完的数据，cur后代表待处理的数据。dest前代表非0数字，dest后为0数字。
n为数组长度，数据会被划分为三个区间，[0,dest]为处理后非零，[dest+1,cur-1]为处理后0，[cur，n-1]为待处理。
执行逻辑：cur在从前向后遍历的过程中，如果遇到0将该元素留在第二个区间 cur++，如果遇到非0证明要把该元素换到第一个区间则dest++，置换nums[cur]和nums[dest]后cur++。
class Solution {
public void moveZeroes(int[] nums) {
int cur=0,dest=-1;
while(cur<nums.length){
if(nums[cur]==0){
cur++;
}else{
dest++;
int temp=nums[dest];
nums[dest]=nums[cur];
nums[cur]=temp;
cur++;
}
}
}
}扩展：该思想同样适用于快排，快排时会找到一个标志数temp，要求temp左边的元素小于ntemp,右边的元素大于temp。和左边非0右边0其实是一样的，只需要替换if中的条件即可。
2、复写零
链接：https://leetcode.cn/problems/duplicate-zeros/submissions/588110496/
本题虽然显示是简单，但是非常难，先根据异地移动思考，转化为就地操作。从前往后遍历会出问题，所以从后往前遍历，先要确定好cur的位置，画图做，很难想。
class Solution {
public void duplicateZeros(int[] arr) {
int cur=0,dest=0;
int n=arr.length;
//找到开始反向操作的节点
while(cur<=n){
//到末尾处会出现两种情况
if(dest==n){
cur--;
dest--;
break;
}
if(dest==n+1){
arr[dest-2]=0;
dest-=3;
cur-=2;
break;
}
if(arr[cur]!=0){
dest++;
}else{
dest+=2;
}
cur++;
}
//开始反向遍历
while(cur>=0){
if(arr[cur]!=0){
arr[dest]=arr[cur];
cur--;
dest--;
}else{
arr[dest--]=0;
arr[dest--]=0;
cur--;
}
}
}
}3、快乐数
链接：https://leetcode.cn/problems/happy-number/
本题有两种情况，一种是变成1，另一种是无限循环，也就是说某次计算后变成了之前出现过的数字。1再经过计算后还是1，所以这也可以看做是一种循环。所以本题最后的结果可以看作两种循环，一种循环里没有1，一种循环里全是1，我们只要判断循环里是否有1就行了。那么第一步就是进入到循环，在hot100中有一道环形链表的题，通过那到题的思路我们可以想到，想要进入到循环要使用快慢指针。
class Solution {
//定义一个计算一个数各位平方和的函数
public int bit_square(int n) {
int sum=0;
while(n!=0){
int m=n%10;
sum+=m*m;
n=n/10;
}
return sum;
}
public boolean isHappy(int n) {
int slow=n;
int fast=bit_square(n);
while(slow!=fast){
slow=bit_square(slow);
fast=bit_square(bit_square(fast));
}
if(slow==1){
return true;
}else{
return false;
}
}
}4、盛最多水的容器
链接：https://leetcode.cn/problems/container-with-most-water/description/
这道题首先想到的是用暴力求解法，也就是遍历一遍，把所有的值计算一边找出最大的，但这样做会超时。然后我们可以尝试找一下规律，发现计算两个位置的体积后，那个高度较小的位置与这两个位置之间的任何位置的体积都比原来小。所以我们直接选择两个端点，在计算后高度较小的那个数直接排除掉，向左和向右平移即可。
class Solution {
public int maxArea(int[] height) {
int left=0,right=height.length-1,res=0;
while(left<right){
int volume=(right-left)*Math.min(height[left],height[right]);
res=Math.max(volume,res);
if(height[left]<height[right]){
left++;
}else{
right--;
}
}
return res;
}
}5、有效三⻆形的个数
链接：https://leetcode.cn/problems/valid-triangle-number/submissions/588461959/
解法一：暴力求解
用暴力求解可以遍历所有的可能，然后把满足要求的加到一起，时间复杂度为N^3.
解法二：双指针
三角形的判定条件为两边之和大于第三边，我们没必要判别三次，只要保证最小的两条边大于第三边即可，这样只需要判别一次，所以在最开始先给数据排序。
class Solution {
public int triangleNumber(int[] nums) {
Arrays.sort(nums);
int count=0;
//从数组最右侧开始遍历，每次把数组的最右侧设为标志位，判断剩下的数里有多少种两个数的组合和它能构成三角形
for(int i=nums.length-1;i>=2;i--){
int left=0,right=i-1;
while(left<right){
//如果此时满足是大于，那么left和right中间的的数和right处的数构成的组合也一定满足要求
if(nums[left]+nums[right]>nums[i]){
count+=right-left;
right--;
}else{
//如果此时是小于，那么left和right中间的的数和left处的数构成的组合一定不满足要求
left++;
}
}
}
return count;
}
}使用双指针时间复杂度为N^2。
6、和为s的两个数字
链接：https://leetcode.cn/problems/he-wei-sde-liang-ge-shu-zi-lcof/description/
本题题目已经说了升序，用双指针可以很轻松的做出来。
class Solution {
public int[] twoSum(int[] price, int target) {
int left=0,right=price.length-1;
while(left<right){
if(price[left]+price[right]==target){
return new int[]{price[left],price[right]};
}else if(price[left]+price[right]>target){
right--;
}else{
left++;
}
}
return new int[2];//照顾编译器，必须有返回值
}
}7、三数之和
链接：https://leetcode.cn/problems/3sum/
借助上一道题两数之和的思想，这道题可以类比。我们可以先排序（方便去重，数组里只要保存着相同的元素就算顺序不一样也算重复），然后固定最开始的元素作为数a，然后从后面找两个数的和等于a的相反数，就转化为了两数之和。然后取第二个数为数a，再找后面的相加为a的相反数的两个数，重复这个操作。
这道题注意要去重，找到⼀个结果之后， left 和 right 指针要跳过重复的元素，当使⽤完⼀次双指针算法之后，固定的 a 也要跳过重复的元素。
8、四数之和
链接：https://leetcode.cn/problems/4sum/
结合三数之和和两数之和的思想，可以很轻松的做出来，这道题有个坑是他弄了一个很大的数，所以需要用long来存。
class Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {
List<List<Integer>> res=new ArrayList<>();
Arrays.sort(nums);
int n=nums.length;
for(int i=0;i<=n-4;){
long target1=target-nums[i];
for(int j=i+1;j<=n-3;){
int left=j+1,right=n-1;
long target2=target1-nums[j];
while(left<right){
long sum=nums[left]+nums[right];
if(sum<target2){
left++;
}else if(sum>target2){
right--;
}else{
res.add(new ArrayList(Arrays.asList(nums[left],nums[right],nums[i],nums[j])));
left++;
right--;
while(nums[left-1]==nums[left]&&left<right){
left++;
}
while(nums[right+1]==nums[right]&&left<right){
right--;
}
}
}
j++;
while(nums[j-1]==nums[j]&&j<=n-3){
j++;
}
}
i++;
while(nums[i-1]==nums[i]&&i<=n-4){
i++;
}
}
return res;
}
}