双指针

双指针是一种常用且简洁的数据结构，通过维护两个指针/下标/列表，动态地存储原数据的关键信息，在需要时进行快速的调取；往往可以降低空间复杂度

例题

移动零

题目

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

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

示例 1:

输入: nums = [0,1,0,3,12]
输出: [1,3,12,0,0]

示例 2:

输入: nums = [0]
输出: [0]

提示:

• 1 <= nums.length <= 104
• -231 <= nums[i] <= 231 - 1

分析

解法一：采用双指针。维护两个指针，其中左指针指向要处理的数，右指针指向已处理完成的数组尾部；一开始两个指针均在数组开始，左指针不断右移，每当遇到非零数，就交换左右指针的数值，同时右指针右移一位，遇到零则跳过。这样总可以保证右指针要么与左指针一同移动——无事发生，要么停在零上，即指向要放到尾部的元素，这样每次和左指针交换时总倾向于把0放到之后的位置，当左指针遍历到数组尾部，右指针一定已经将最后一个0换到尾部；而交换非零数的时候总是先访问者先交换，因此在前面的元素（非0）一定先被交换到前面，在后面的元素被交换后仍在之前就在他前面元素的后面，这样就保证了非0数相对顺序。

代码如下

class Solution {
   public void moveZeroes(int[] nums) {
        // 使用双指针
        int right = 0;
        for (int left = 0; left < nums.length; left++) {
            if (nums[left] != 0) {
                // swap
                int tmp = nums[left];
                nums[left] = nums[right];
                nums[right] = tmp;
                right++; // 更新右指针
            }
        }
    }
}

解法二：本题双指针不是必须的，不用双指针也有很便捷的方法。注意到题目将要放到数组尾部的元素总是$0$（确定值），因此我们完全可以任意覆盖该元素，最后将空缺出来的位置填上0即可。换句话说，我们只需要维护一个指针 $i$ 和一个计数器 $cnt$，$cnt$记录非零值的个数（应当填入的数组位置）；指针 $i$ 一开始位于头部，之后不断右移，每次遇到零值就跳过，遇到非零值就将它放入计数器指示的位置。由于 $cnt <= i$恒成立，因此在一个非零值被覆盖前（$cnt$占用）一定会先访问到（$i >= cnt$），除了被跳过的$0$，而0是一个确定值，只需要在所有非零值都处理完后将空缺位置填入$0$即可。按顺序遍历也保证了相对顺序。

代码如下

class Solution {
   public void moveZeroes(int[] nums) {
        int cnt = 0;
        for (int i = 0; i < nums.length; i++) {
            // 非0元素前移，剩余位置全部填0
            // 因为填入的是固定值，所以直接覆盖也没有关系，而非零值的当前下标一定小于等于最终的下标，所以非零值一定不会被提前覆盖
            if (nums[i] != 0) {
                nums[cnt++] = nums[i]; // cnt <= i, 因此再覆盖一个元素前一定会先访问，这样非零元素总会被安排到正确的位置
            }
        }
        for (int i = cnt; i < nums.length; i++) {
            nums[i] = 0;
        }
    }
}

盛最多水的容器

题目

给定一个长度为 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 <= 105
• 0 <= height[i] <= 104

分析

我们考虑夹逼法：从两端开始不断向中间收缩。不难发现收缩时容器的宽度一定会减小，所以只有容器的**有效高度（两边器壁高度的较小者）**变大，容器的容量才有可能变大，即让两侧高度中较小的一侧向内收缩，这样才有机会取得更大值，如果选择让较大者收缩，那之后的高度一定不会高于较小一侧的高度（目前的高度），再加上宽度一定减小，因此容量一定变小，这是不可行的。因此维护两个指针 $left$ 和 $right$ ，一开始 $left$ 指向最左侧 $right$ 指向最右侧，每次让高度较小一侧的指针向内收缩（$left++$ or $right--$），尝试取到更大的容量。当两个指针相遇，即宽度减为$0$时，算法结束。

代码如下

class Solution {
  public int maxArea(int[] height) {
        // 装水遵循木桶原则，即短板是上限
        // 利用左右两个指针从边界开始夹逼

        /* 每次总是固定较长的那个柱子，移动较短的那个柱子 -- 因为向中间收缩时，宽度一定降低，只有提高高度才有可能变大
           如果移动较长的柱子，那么后面的宽度一定不会大于较短的柱子，再加上宽度一定减小，所以容量一定变小
           所以只能移动较短的柱子，这样之后的高度仍是不确定的，可能超过当前容量（在宽度减小的情况下）
           当两根柱子相遇，结束算法 */

        int max = 0;
        int right = height.length - 1, left = 0;
        while (right > left) {
            max = Math.max(Math.min(height[right], height[left]) * (right - left), max);
            if (height[left] > height[right]) {
                // 左边高，移动右边
                right--;;
            } else {
                left++;
            }
        }
        return max;
    }
}

三数之和

题目

给你一个整数数组 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
• -105 <= nums[i] <= 105

分析

本题关键在于去重。首先对数组进行排序（此处采用升序），之所以先进行排序，是因为可以让重复的元素连在一起，方便之后跳过；同时也可以利用大小有序、分离正负的排序效果去除一些必然不成立的情况。

因为三元组的特殊性，我们首先固定一个元素来减少变动元素的数量，这样就只需要考虑两个元素的和 $sum$，每次这两个元素都从固定元素之后的数组中取（从之前取一定会重复，因为前面的已经固定过了）；又由于数组已经有序即从小到大排列，所以当固定的数值为正数时，后面的数必然都是正数，三数之和不可能为0，此时算法结束。当固定的数非正时，我们只需要剩下两个数的和为固定数的相反数 $target$ 即可；因此维护两个指针 $left$ 和 $right$，一开始$left$ 指向固定数左侧数组的最左侧，$right$指向最右侧，不难发现当收缩 $left$时 $sum$会增大，反之收缩收缩 $right$时 $sum$会减小，利用这个特点，只要$right > left$ （指针不相遇，这一趟固定扫描尚未结束） 我们就重复做

• $sum == target$ 获取一个三元组，同时左边界和右边界收缩直到跳过所有和刚才指向的元素相同的元素，注意保持$right > left$
• $sum > target$ 收缩右边界 即 $right--$
• $sum < target$ 收缩左边界 即 $left++$

每次循环最后要更新 $sum$ 的值

当固定一个数之后的所有三元组获取结束后，要跳过之后所有和这个数相同的元素来防止重复。

总结：

• 当固定的数值为正数时，算法结束
• 固定完一个数，跳过之后所有相同的数之后再固定下一个数
• 获取完三元组后收缩左右边界跳过和刚才获取的三元组中相同的数
• 固定一个数时的循环保证 $right > left$

代码如下

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        if (nums.length < 3) {
            return new ArrayList<>();
        }
        Arrays.sort(nums);
        List<List<Integer>> ans = new ArrayList<>();
        for (int i = 0; i < nums.length - 2; i++) {
            if (nums[i] > 0) {
                break; // 因为数组已经有序，所以若当前数字为正，后面不可能抵消出负数，不可能再有成立的情况; 算法结束
            }
            if (i > 0 && nums[i] == nums[i - 1]) { 
                // 且若前面有一个和自己一样的，自己会重复，跳过
                continue;
            }
            // 先固定一个
            int target = -nums[i];
            // 启动双指针，相向而行
            int left = i + 1, right = nums.length - 1;
            int sum = nums[left] + nums[right];
            while (left < right) {
                // 由于数组有序，所以right--和会变小，left++和会变大
                if (sum > target) {
                    // sum需减小
                    // 要跳过所有一样的, 降低复杂度
                    int old = nums[right];
                    while (nums[right] == old && left < right) {
                        right--;
                    }
                } else if (sum < target) {
                    int old = nums[left];
                    while (nums[left] == old && left < right) {
                        left++;
                    }
                } else {
                    ArrayList<Integer> group = new ArrayList<>();
                    group.add(nums[i]);
                    group.add(nums[left]);
                    group.add(nums[right]);
                    // 找到了一个可能的三元组，只要不重复
                    ans.add(group);
                    // 跳过之后/前所有还会重复的
                    while (left < right && nums[left] == nums[left + 1]) {
                        left++;
                    }
                    while (left < right && nums[right] == nums[right - 1]) {
                        right--;
                    }
                    if (left < right) {
                        left++;
                        right--;
                    }
                }
                sum = nums[left] + nums[right];
            }
        }
        return ans;
    }
}

接雨水

注：本题主体应当属于动态规划，双指针只是用来优化空间复杂度，不必须

题目

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

示例 1：

输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。 

示例 2：

输入：height = [4,2,0,3,2,5]
输出：9

提示：

• n == height.length
• 1 <= n <= 2 * 104
• 0 <= height[i] <= 105

分析

我们将这个问题分解，整体存雨水的量等于所有坐标处存的雨水量之和，而每个坐标处的雨水量该怎么求呢？观察发现每个坐标处的宽度都是1，因此坐标处的雨水量就是该坐标处雨水能达到的高度。结合木桶效应，一个位置的水位能达到的最高处等于它两侧器壁中的较小者再减去此坐标处柱子的高度（柱子排水），如果小于0，就是0；因为此处柱子是连续的，所以一个位置左侧器壁终结于左边最长的一根柱子，右侧器壁终结于右侧最高的柱子。

由此该问题退化为：找每个位置的左侧最高柱子和右侧最高柱子，取小的最高水位，再减去自己的柱子长度的实际水位，如果小于0就没有水，所有位置加起来即最终结果。

求每个位置的左/右侧最高柱子可用迭代法：每个位置的左/右侧最高柱子就两种情况

• 左/右边的那根柱子
• 左/右边那根柱子的左/右侧最高柱子

取两者中较大者即可

代码如下

class Solution {
    public int trap(int[] height) {
        // 先找到两侧最高柱子
        /* 用迭代法计算每个位置左/右侧柱子的最大值
              以左侧柱子为例，位置i的左侧柱子最大值为i - 1处柱子最大值和i - 1处高度中的较大者
         */
        int ans = 0; // 最终用于求和
        // 迭代法求两侧最高柱子
        int[] left = new int[height.length], right = new int[height.length];
        left[0] = 0;
        for (int i = 1; i < height.length; i++) {
            left[i] = Math.max(height[i - 1], left[i - 1]); // 左边或左边的左侧的最高柱子
        }
        right[height.length - 1] = 0;
        for (int i = height.length - 2; i >= 0; i--) {
            right[i] = Math.max(height[i + 1], right[i + 1]); // 右边或右边的右侧最高柱子
        }
        // 计算每个位置的水量
        for (int i = 0; i < height.length; i++) {
            // each = max(0, min(left, right) - self_h);
            ans += Math.max(0, Math.min(left[i], right[i]) - height[i]);
        }
        return ans;
    }
}

优化：双指针

class Solution {
public:
    int trap(vector<int>& height) {
        // 双指针，一个维护左边最大，一个维护右边最大，每次动小的那边，因为高度不可能比短的高
        int left = 0, right = height.size() - 1, lh = height[0], rh = height.back();
        int ans = 0;
        while (left <= right) {
            if (lh < rh) {
                ans += max(0, lh - height[left]);
                lh = max(lh, height[left]);
                left++;
            } else {
                ans += max(0, rh - height[right]);
                rh = max(rh, height[right]);
                right--;
            }
        }
        return ans;
    }
};

(•‿•)