【Java 刷题记录】双指针

双指针

1. 移动零

283. 移动零 - 力扣（LeetCode）

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

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

示例 1:
输入: nums = [0,1,0,3,12]
输出: [1,3,12,0,0]
示例 2:
输入: nums = [0]
输出: [0]
提示:

1 <= nums.length <= 104
-2³¹ <= nums[i] <= 2³¹ - 1

**进阶：**你能尽量减少完成的操作次数吗？

class Solution {
    public void moveZeroes(int[] nums) { 
        int cur = 0;
        int dest = -1;
        int n = nums.length;
        while(cur < n) {
            if(nums[cur] != 0) {
                dest++;
                int tmp = nums[dest];
                nums[dest] = nums[cur];
                nums[cur] = tmp;
            }
            cur++;
        }
    }
}

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 <= arr.length <= 104
0 <= arr[i] <= 9

class Solution {
    public void duplicateZeros(int[] arr) {
        // 1. 找到最后一个复写的数
        int cur = 0;
        int n = arr.length;
        int dest = -1;
        while(dest < n - 1) {
            dest += arr[cur] == 0 ? 2 : 1;
            if(dest < n - 1) {
                cur++;
            }
        }
        // 从后往前复写
        // 规避特殊情况
        if(dest == n) {
            arr[dest - 1] = 0;
            cur --;
            dest -= 2;
        }
        while(cur >= 0) {
            if(arr[cur] != 0) {
                arr[dest--] = arr[cur--];
            }else {
                arr[dest] = 0;
                arr[dest - 1] = 0;
                cur--;
                dest -= 2;
            }
        }
    }
}

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 <= n <= 2³¹ - 1

class Solution {

    public int function(int n) {
        int sum = 0;
        while(n != 0) {
            int num = n % 10;
            sum += num * num;
            n /= 10;
        }
        return sum;
    }

    public boolean isHappy(int n) {
        int num1 = n;
        int num2 = n;
        while(true) {
            num1 = function(num1);
            num2 = function(function(num2));
            if(num1 == num2) {
                return num1 == 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
提示：

n == height.length
2 <= n <= 10⁵
0 <= height[i] <= 10⁴

class Solution {
    public int maxArea(int[] height) {
        int n = height.length;
        int left = 0;
        int right = n - 1;
        int ret = 0;
        while(left < right) {
            int h = 0;
            if(height[left] < height[right]) {
                h = height[left];
                left++;
            }else {
                h = height[right];
                right--;
            }
            ret = Math.max(ret, (right - left + 1) * h);
        }
        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 <= nums.length <= 1000
0 <= nums[i] <= 1000

class Solution {

    public int getValidNumber(int[] nums, int left, int right, int flag) {
        int sum = 0;
        while(left < right) {
            if(nums[left] + nums[right] > flag) {
                sum += right - left;
                right--;
            }else {
                left++;
            }
        }
        return sum;
    }

    public int triangleNumber(int[] nums) {
        Arrays.sort(nums);
        int sum = 0;
        for(int i = nums.length - 1; i >= 2; i--) {
            sum += getValidNumber(nums, 0, i - 1, nums[i]);
        }
        return sum;
    }
}

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 <= price.length <= 10^5
1 <= price[i] <= 10^6
1 <= target <= 2*10^6

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

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 。
提示：

3 <= nums.length <= 3000
-10⁵ <= nums[i] <= 10⁵

class Solution {

    public void culAndAdd(int[] nums, List<List<Integer>> list, int left, int right, int flag) {
        while(left < right) {
            int sum = nums[left] + nums[right] + flag;
            if(sum > 0) {
                right--;
                while(right > left && nums[right] == nums[right + 1]) right--;
            }else if(sum < 0) {
                left++;
                while(left < right && nums[left] == nums[left - 1]) left++;
            }else {
                list.add(Arrays.asList(nums[left++], nums[right--], flag));
                while(left < right && nums[left] == nums[left - 1]) left++;
                while(right > left && nums[right] == nums[right + 1]) right--;
            }
        }
    }

    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        int n = nums.length;
        List<List<Integer>> list = new ArrayList<>();
        for(int i = n - 1; i >= 2;) {
            if(nums[i] < 0) {
                break;
            }
            culAndAdd(nums, list, 0, i - 1, nums[i]);
            i--;
            while(i >= 2 && nums[i] == nums[i + 1]) i--;
        }
        return list;
    }
}

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 <= nums.length <= 200
-10⁹ <= nums[i] <= 10⁹
-10⁹ <= target <= 10⁹

class Solution {

    public void calAndAdd(int[] nums, List<List<Integer>> list, int left, int right, int flag1, int flag2, int target) {
        while(left < right) {
            long sum = 0L + nums[left] + nums[right] + flag1 + flag2;
            if(sum > target) {
                right--;
                while(left < right && nums[right] == nums[right + 1]) right--;
            }else if(sum < target) {
                left++;
                while(left < right && nums[left] == nums[left - 1]) left++;
            }else {
                list.add(Arrays.asList(nums[left++], nums[right--], flag1, flag2));
                while(left < right && nums[right] == nums[right + 1]) right--;
                while(left < right && nums[left] == nums[left - 1]) left++;
            }
        }
    }

    public List<List<Integer>> fourSum(int[] nums, int target) {
        Arrays.sort(nums);
        int n = nums.length;
        List<List<Integer>> list = new ArrayList<>();
        if(n < 4) {
            return list;
        }
        for(int i = n - 1; i >= 3;) {
            if(nums[i] < 0 && nums[i] <= target) {
                break;
            }
            for(int j = i - 1; j >= 2;) {
                if(nums[j] < 0 && nums[j] <= target - nums[i]) {
                    break;
                }
                calAndAdd(nums, list, 0, j - 1, nums[j], nums[i], target);
                j--;
                while(j >= 2 && nums[j] == nums[j + 1]) j--;
            }
            i--;
            while(i >= 3 && nums[i] == nums[i + 1]) i--;
        }
        return list;
    }
}