力扣top100-双指针

---

283.移动零

283.移动零

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

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

方法一

把非零数值移动到前面，剩下的直接赋值为0。

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

方法二

双指针。非0数值，交换数据，左右指针都往右移；若为0，右指针右移。

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

11.盛水最多的容器

11.盛水最多的容器

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。

找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。返回容器可以储存的最大水量。

说明：你不能倾斜容器。

方法一

在每个状态下，无论长板或短板向中间收窄一格，都会导致水槽 底边宽度 −1-1−1 变短：

• 若向内 移动短板 ，水槽的短板 min(h[i],h[j])min(h[i], h[j])min(h[i],h[j]) 可能变大，因此下个水槽的面积 可能增大 。
• 若向内 移动长板 ，水槽的短板 min(h[i],h[j])min(h[i], h[j])min(h[i],h[j]) 不变或变小，因此下个水槽的面积 一定变小 。

双指针 l, r分列水槽左右两端；选取l和r中较小的一个向内移动。

class Solution {
    public int maxArea(int[] height) {
        int l = 0, r = height.length - 1;
        int res = 0;
        while (l < r) {
            res = height[l] < height[r] ?
                    Math.max(res, (r - l) * height[l++]):
                    Math.max(res, (r - l) * height[r--]);
        }
        return res;
    }
}

15.三数之和

15.三数之和

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。

注意：答案中不可以包含重复的三元组。

• 先将 nums 排序，固定 3个指针中最左（最小）元素的指针 i，双指针 l，r分设在数组索引 (i,len(nums)) 两端
• 双指针 l, r 交替向中间移动，记录对于每个固定指针 i的所有满足 nums[i] + nums[l] + nums[r] == 0 的 l,r组合：
• 当 nums[i] > 0 时直接break，因为 nums[r] >= nums[l] >= nums[i] > 0，即 3 个元素都大于 0 ，在此固定指针 i之后不可能再找到结果了。
• 当 i > 0且nums[i] == nums[i- 1]时即跳过此元素nums[i]，因为已经将 nums[k - 1] 的所有组合加入到结果中，本次双指针搜索只会得到重复组合。
• 当l < r 时循环计算s = nums[i] + nums[l] + nums[r]，并按照以下规则执行双指针移动：
  当s < 0时，l++并跳过所有重复的nums[l]；
  当s > 0时，r–并跳过所有重复的nums[r]；
  当s == 0时，记录组合[i, l, r]至res，执行l++和r–并跳过所有重复的nums[l]和nums[r]，防止记录到重复组合。

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> ans = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > 0) {  // nums[i] > 0,那靠右边的两个数肯定也是大于0，加起来也是大于0
                break;
            }
            //过滤重复的值
            if (i > 0 && nums[i - 1] == nums[i]) {
                continue;
            }
            //先固定i，再设置双指针在区间的两侧
            int l = i + 1, r = nums.length - 1;
            while (l < r) {
                int s = nums[i] + nums[l] + nums[r];
                if (s == 0) {
                    ans.add(Arrays.asList(nums[i], nums[l], nums[r]));
                    //过滤重复的nums[l] nums[r]
                    while (l < r && nums[l] == nums[l + 1]) {
                        l++;
                    }
                    while (l < r && nums[r] == nums[r - 1]) {
                        r--;
                    }
                    l++;
                    r--;
                } else if (s > 0) {
                    r--;
                } else {
                    l++;
                }
            }
        }
        return ans;
    }
}

接雨水

42.接雨水

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

方法一：动态规划

当前列可以承载的雨滴数=min(当前列左边的最高列，当前列右边的最高列) - 当前列的大小。
可以定义两个数组记录第i列左边的最高列和右边的最高列。

class Solution {
    public int trap(int[] height) {
        /**
         *  当前列可以承载的雨滴数= min(当前列左右两侧的最大值)-当前列的大小；
         *  就是当前这个列的左边最高列和右边最高列中的最小那个 与 本列的差值   是否大于>0
         */
        int sum = 0;
        int[] left = new int[height.length];
        int[] right = new int[height.length];
        for (int i = 1; i < height.length - 1; i++) {
            left[i] = Math.max(left[i - 1], height[i - 1]);
        }
        for (int i = height.length - 2; i >= 0; i--) {
            right[i] = Math.max(right[i + 1], height[i + 1]);
        }
        for (int i = 1; i < height.length - 1; i++) {
            int min = Math.min(left[i], right[i]);
            if (min > height[i]) {
                sum = sum + min - height[i];
            }
        }
        return sum;
    }
}

方法二：双指针

可以看到，left [ i ] 和right [ i ] 数组中的元素只用一次。所以我们可以只用一个元素代替。例如第一个循环和第三个for循环的方向是一样的，于是可以定义一个max_left来代替left[i]。

public int trap(int[] height) {
    int sum = 0;
    int max_left = 0;
    int[] right = new int[height.length];
    for (int i = height.length - 2; i >= 0; i--) {
        right[i] = Math.max(right[i + 1], height[i + 1]);
    }
    for (int i = 1; i < height.length - 1; i++) {
        max_left = Math.max(max_left, height[i - 1])
        int min = Math.min(max_left, right[i]);
        if (min > height[i]) {
            sum = sum + min - height[i];
        }
    }
    return sum;
}

但是right[i]数组是从右到左遍历的，所以可以使用双指针。当左边列的值更小时，就从左到右遍历；当右边列的值更小时，就从右到左遍历。

public int trap(int[] height) {
    int sum = 0;
    int max_left = 0;
    int max_right = 0;
    int left = 1, right = height.length - 2;
    for (int i = 1; i < height.length - 1; i++) {
        if (height[left - 1] < height[right + 1]) {
            max_left = Math.max(max_left, height[left - 1])
        	int min = max_left;
            if (min > height[left]) {
                sum = sum + min - height[left];
            }
            left++;
        } else {
            max_right = Math.max(max_right, height[right + 1])
        	int min = max_right;
            if (min > height[right]) {
                sum = sum + min - height[right];
            }
            right--;
        }
    }
    return sum;
}