LeetCode-数组-双指针-中等难度

双指针

双指针一般是指利用两个变量，通过在线性的结构上进行遍历来解决某些特定的问题，按照遍历的方式一般多采用：同向遍历，相向遍历两种方式，例如冒泡排序、选择排序、插入排序都是用了两个变量同向遍历来实现，快排则是通过相向遍历来实现。

1. 删除有序数组中的重复项（入门）

1.1 题目描述

1.2 解题思路

快慢指针的简单应用

1.3 代码实现

public int removeDuplicates(int[] nums) {
    int n = nums.length;
    int p1 = 0;
    int p2 = 1;
    while (p2 < n) {
        if (nums[p1] != nums[p2]) {
            nums[++p1] = nums[p2];
        }
        p2++;
    }
    return p1 + 1;
}

leetcode跳转：26. 删除有序数组中的重复项

2. 删除有序数组中的重复项 II（简单）

2.1 题目描述

2.2 解题思路

与前一题结合在一起看，就是保留前X个相同数字，超过X个后，再进行比较，所以快指针逻辑不变，只需要让慢指针在比较时每次往前取两位即可。

2.3 代码实现

public int removeDuplicates(int[] nums) {
    int n = nums.length;
    if (n <= 2) {
        return n;
    }
    int p1 = 2;
    int p2 = 2;
    while (p2 < n) {
        if (nums[p1 - 2] != nums[p2]) {
            nums[p1] = nums[p2];
            p1++;
        }
        p2++;
    }
    return p1;
}

leetcode跳转：80. 删除有序数组中的重复项II

3. 移动零（简单）

3.1 题目描述

3.2 代码实现

public void moveZeroes(int[] nums) {
    int zero = 0;
    for (int i = 0; i < nums.length; i++) {
        if (nums[i] != 0) {
            int t = nums[i];
            nums[i] = 0;
            nums[zero] = t;
            zero++;
        }
    }
}

leetcode跳转：283. 移动零

4. 两数之和（入门）

4.1 题目描述

4.2 解题思路

左右指针，相向遍历

4.3 代码实现

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

leetCode跳转：167. 两数之和 II - 输入有序数组

5. 盛水最多的容器（中等）

5.1 题目描述

5.2 解题思路

同样是一道左右指针，相向遍历的题，每次移动较短的柱子，盛水最多的容器，即为：间距 * min(left, right)

5.3 代码实现

public int maxArea(int[] height) {
    int n = height.length;
    int left = 0;
    int right = n - 1;
    int ans = 0;
    while (left < right) {
        int min = Math.min(height[left], height[right]);
        ans = Math.max(ans, min * (right - left));
        if (height[left] < height[right]) {
            left++;
        } else {
            right--;
        }
    }
    return ans;
}

leetCode跳转：11. 盛水最多的容器

6. 三数之和（中等）

6.1 题目描述

6.2 解题思路

排序+双指针也是常见的组合解法，本题只需要排序后，再进行枚举即可。

两处优化

6.3 代码实现

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

leetCode跳转：15. 三数之和

7. 最接近的三数之和（中等）

7.1 题目描述

7.2 解题思路

解法同三数之和

7.3 代码实现

public int threeSumClosest(int[] nums, int target) {
    Arrays.sort(nums);
    int ans = Integer.MAX_VALUE;
    int n = nums.length;
    for (int i = 0; i < n - 2; i++) {
        int j = i + 1;
        int k = n - 1;
        while (j < k) {
            int sum = nums[i] + nums[j] + nums[k];
            if (sum == target) {
                return sum;
            }
            // 接近三数之和
            if (Math.abs(sum - target) < Math.abs(ans - target)) {
                ans = sum;
            }
            if (sum > target) {
                k--;
            } else {
                j++;
            }
        }
    }
    return ans;
}

leetCode跳转：16. 最接近的三数之和

8. 接雨水（中等）

8.1 题目描述

8.2 解题思路

左右指针，相向遍历。
要求可接的雨水处的水量，可以先分别求出位于此处两侧最长柱子的高度，然后取其较短的一根即表示其可接水量的上限，因此完全可以通过不断的左右遍历（收缩较短的柱子）的方式计算出每个位置可接的水量。

8.3 代码实现

public int trap(int[] height) {
    int n = height.length;
    int leftMax = 0;
    int rightMax = 0;
    int left = 0;
    int right = n - 1;
    int ans = 0;
    while (left < right) {
        leftMax = Math.max(leftMax, height[left]);
        rightMax = Math.max(rightMax, height[right]);
        if (height[left] < height[right]) {
            ans += leftMax - height[left];
            left++;
        } else {
            ans += rightMax - height[right];
            right--;
        }
    }
    return ans;
}

leetCode跳转：42. 接雨水