优选算法精品——双指针

移动零

算法原理：

1.数组划分,数组分块

2.双指针算法

(利用数组下标来充当指针)

两个指针的作用:

cur:从左往右扫描数组,遍历数组

dest:已处理的区间内,非零元素的最后一个位置

代码实现：

class Solution {
    public void move(int[] nums) {
        for (int cur = 0, dest = -1; cur < nums.length; cur++) {
            if (nums[cur] != 0) {
                dest++;
                // 交换当前元素与目标位置的元素
                int temp = nums[cur];
                nums[cur] = nums[dest];
                nums[dest] = temp;
            }
        }
    }
}

复写零

2.算法原理

解法:双指针算法

先根据“异地”操作,然后优化成双指针下的“就地”操作，先找到最后一个“复写”的数;

双指针算法

1.先判断 cur位置的值

2. 决定dest向后移动一步或者两步

3.判断一下dest是否已经到结束为止

4. cur++

1.5处理一下边界情况

代码：

class Solution {
    public void duplicateZeros(int[] arr) {
        int n = arr.length;
        int top = 0;
        int i = -1;
        while (top < n) {
            i++;
            if (arr[i] != 0) {
                top++;
            } else {
                top += 2;
            }
        }
        int j = n - 1;
        if (top == n + 1) {
            arr[j] = 0;
            j--;
            i--;
        } 
        while (j >= 0) {
            arr[j] = arr[i];
            j--;
            if (arr[i] == 0) {
                arr[j] = arr[i];
                j--;
            } 
            i--;
        }
    }
}

快乐数

题目解析：

算法原理

1第一种情况不是快乐树，那么最后值不为一，且会返回到原来值，形成一个环

2第二种情况是快乐树，那么最后值为一，形成一个全是一的环

因此，我们只需要采用快慢指针法，判断他们相遇时环中值是否为一，若为一则是快乐树，反之

3.代码实现

class Solution {

    public int bitSum(int n) {
        int sum = 0;
        while (n > 0) { // 确保 n 大于 0
            int t = n % 10;
            sum += t * t;
            n = n / 10;
        }
        return sum;
    }

    public boolean isHappy(int n) {
        int slow = n;
        int fast = bitSum(n);
        while (slow != fast) {
            slow = bitSum(slow); // 更新 slow
            fast = bitSum(bitSum(fast)); // 更新 fast
        }
        return slow == 1; // 检查 slow 是否到达 1
    }
}

解析：

盛水最多的容器：

题目解析：

计算两条直线与x轴围成的水的体积，以最低的线计算高

算法原理：

将各个线的高度看作一个数组，采双指针法，分别计算每个容器的体积，并比较出最大的容器

class Solution {
    public int maxArea(int[] height) {
        int left = 0, right = height.length - 1, volume = 0;
        while (left < right) {
            int v = Math.min(height[left], height[right]) * (right - left);
            volume = Math.max(volume, v);
            // 移动较短的边
            if (height[left] < height[right]) {
                left++;
            } else {
                right--;
            }
        }
        return volume;
    }
}

有效三角形的个数

算法原理

1.暴力算法：

for(int i=0;i<arr.length;i++){

for(int j=0;j<arr.length;j++){

for(int k=0;k<arr.length;k++){

check(i,j,k);

}

}

}

2.利用单调性，双指针算法

1.先固定最大的数

2.在最大的左区间内使用双指针算法，统计出三元组的个数

1a+b>c  left=right,right--;

2.a+b<=c  left++

代码实现

public int solution{
Arrays.sort(nums);
int ret=0,n=nums.length;
for(int i=n-1;i>=2;i--){
int left=0,right=i-1;
while(left>right){
if(nums[left]+nums[right]>nums[i]){
ret+=right-left;
right--;

}else{
left++;
}
}
}
return ret;
}

和为s的两个数字

算法原理：
1.暴力算法

for(int i=0;i<arr.length;i++){

for(int j=0;j<arr.length;j++){

check(i,j);

}

}

双指针（与上题同理）

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        int i = 0;
        int j = nums.size() - 1;

        //双指针
        while(i < j){
            auto s = nums[i] + nums[j];
            if(s < target)
                i++;
            if(s > target)
                j--;
            if(s == target)
                return{nums[i], nums[j]};
        }
        
        return {};
    }
};

三数之和

代码原理

解法一：暴力算法：三层嵌套排序

解法二:排序+双指针

1.排序;

2.固定一个数a;

3.在该数后面的区间内,利用“双指针算法”
快速找到两个的和等于-a即可。

处理细节问题:

1.去重

找到一种结果之后,left和 right 指针要跳过重复元素

避免越界

当使用完一次双指针算法之后,i也需要跳过重复元素

2.不漏

找到一种结果之后,不要“停”,缩小区间,继续寻找

import java.util.*;

public class ThreeNumber {
    public List<List<Integer>> threenum(int[] nums) {
        List<List<Integer>> ret = new ArrayList<>();  // 用于存放结果
        int n = nums.length;

        // 对数组进行排序
        Arrays.sort(nums);

        // 遍历数组
        for (int i = 0; i < n - 2; i++) {
            // 跳过重复的i值
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }

            int left = i + 1, right = n - 1;

            // 使用双指针查找合适的三元组
            while (left < right) {
                int sum = nums[i] + nums[left] + nums[right];

                if (sum == 0) {
                    // 找到一个三元组
                    ret.add(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--;
                    }
                } else if (sum < 0) {
                    left++;  // 需要更大的和，左指针右移
                } else {
                    right--; // 需要更小的和，右指针左移
                }
            }
        }

        return ret;  // 返回找到的所有三元组
    }
}

四数之和

算法原理：

解法一：暴力算法：

三层嵌套排序

解法二:排序+双指针

1.依次固定一个数a;

2.在a后面的区间内,利用“三数之和”找到三个数,
使这三个数的和等于 target-a 即可

1.依次固定一个数b;

2.在b后面的区间内,利用“双指针”找到两个数,
使这两个数的和等于 target - a -b即可。

处理细节问题:

1.不重

2.不漏

代码实现

  public class threeNumber {
        public List<List<Integer>> threenum(int[] nums) {
            List<List<Integer>> ret = new ArrayList<>();  // 用于存放结果
            int n = nums.length;

            // 对数组进行排序
            Arrays.sort(nums);

            // 遍历数组
            for (int i = 0; i < n - 2; i++) {
                for (int j = i + 1; j < n;j++){
                    // 跳过重复的i值
                    if (i > 0 && nums[i] == nums[i - 1]) {
                        continue;
                    }

                    int left = i + 1, right = n - 1;

                    // 使用双指针查找合适的三元组
                    while (left < right) {
                        int sum = nums[i] + nums[left] + nums[right];

                        if (sum == 0) {
                            // 找到一个三元组
                            ret.add(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--;
                            }
                        } else if (sum < 0) {
                            left++;  // 需要更大的和，左指针右移
                        } else {
                            right--; // 需要更小的和，右指针左移
                        }
                    }
                    //去重
                    while(j<n&&nums[j]==nums[j-1])j++;
                    
                }
                while(i<n&&nums[i]==nums[i-1])i++;
            }

            return ret;  // 返回找到的所有三元组
        }
    }

到这里竹竹零就要和大家说再见了

希望时光不负赶路人，愿我们做最好的自己！！！

如果您觉得有失偏颇请您在评论区指正，如果您觉得不错的话留个好评再走吧！！

您的鼓励就是对我最大的支持!  ！ ！