二、双指针问题

283、移动零（简单）

题目描述

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

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

示例 1:

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

示例 2:

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

提示:

• 1 <= nums.length <= 10⁴
• -2³¹ <= nums[i] <= 2³¹ - 1

题目思路

对于这道题，基本思路是双指针。
简单来说，就是需要将非0的数字按顺序移动到前面，然后0都移动到后面。

方法1：两次遍历、批量赋值0
从题目要求中我们得知，虽然说是“移动”、把非0的移动到前面，0移动到后面，但实际上，数字就是数字，不存在从A移动到B这一说。
因此第一个方法比较简单：

• 从头到尾遍历一遍、将所有非0的元素依次赋值到前面；
• 依次遍历剩余元素，并赋值为0；

这里，我们使用一张动图：

从图中我们可以看到，定义了两个“指针”：

• 快指针a：从头到尾进行遍历的指针，寻找非0的元素；
• 慢指针b：用于记录非0元素的个数，也即标记当前哪一个数组元素应当被赋值为非0；
  • 当a从头遍历到尾时，b所指的位置，就是最后一个非0元素的位置；
  • 接下来只需要将从b到尾所有元素赋值为0即可；

方法2：一次遍历、直接交换
这种方法稍微有点难理解，属于中等难度范畴，后续如果遇到类似问题还是以解法一为准。

所谓一次遍历，就是我们直接从头到尾遍历一轮，通过直接交换元素的方法来实现非0元素在前、为0元素在后。

这种交换的方法也是使用了双指针的思想，不过总体来说较为复杂，这里同样使用一张动图：

从图中我们可以看到，定义了两个“指针”：

• 快指针a：从头到尾进行遍历的指针，寻找非0的元素；
• 慢指针b：尝试指向为0的元素，而且该元素应当是第一个为0的元素；

之所以是“尝试”，是由于：

• 如果数组没有0，那么快慢指针始终指向同一个位置，此时b并非0；
  • 此时可以自己和自己交换；
  • 也可以直接判断一下nums[b]是否为0，再做交换的判断，本质是一样的；
• 如果数组有0，快指针a先走一步，此时慢指针b对应的就是0。
  • 此时快指针a如果找到非0元素，则直接跟慢指针b对应的0交换即可；

a和b一起走，如果数字非0，则二者一起向前走一步；
如果没有遇到0，a和b是在一起同步向前走的；
如果遇到数字为0，则b在0处等待，a继续向前走，寻找下一个非0的元素；
当a找到后，直接将a和b位置的数字交换，并且一起向前走一步，持续上述判断与处理步骤，直到a到达尾部；
b所代表的就是当前已经处理好的序列的尾部，a代表的则是待处理序列的头部，并且：

• b左侧都是非0数；
• b到a都是0；

此时可能会有疑惑：

• 会不会出现a、b同时指向非0元素、但中间有很多0？

不可能出现，这是由于本身a、b移动的性质决定：

• a在每一轮循环都会向前走一步；
• b只有在a不为0时才会向前走一步；
  • 这是由于只要a不为0，我们都会尝试去进行交换（也可先做非0判断）；
  • 该轮交换后b一定要指向下一个待交换元素；
  • 由此确保b左侧的元素全部都是满足题设条件的；

这样的性质决定了，a领先b的步数就是a和b之间0的个数，也即：b到a之间都是0。
只有一开始没有0、以及中间就一个0的情况下，a、b会相遇并同时指向非0，其他情况下，b所指向的一定是0，也即b代表了“已经处理好的序列的尾部”。
例子如下，简单用双指针走一遍就很好理解了：

• [1, 2, 0, 3]
• [1, 2, 0, 0, 3, 4]
• [0, 1, 2, 3, 4]

因此，方法二本质上是一个循环不变量：

• 在每一次循环前，b的左边全部都是不等于0的；
  • 起始b为0，明显满足；
  • 此后每一次循环中：
    • 若nums[a] = 0，则b保持不变，满足；
    • 若nums[a] != 0，交换后b增一，仍然满足

附带官方的解释：

使用双指针，左指针指向当前已经处理好的序列的尾部，右指针指向待处理序列的头部。
右指针不断向右移动，每次右指针指向非零数，则将左右指针对应的数交换，同时左指针右移。
注意到以下性质：
1、左指针左边均为非零数；
2、右指针左边直到左指针处均为零。
因此每次交换，都是将左指针的零与右指针的非零数交换，且非零数的相对顺序并未改变。

算法代码

1、两次遍历、批量赋值0

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
		# nums长度大于等于1，当为1时不需要移动
        if len(nums) == 1:
            return

		# 第一轮遍历时，left的大小本质上是非0元素的个数，只要是非0的数字统统赋值给nums[left]
        left = 0
        for right in range(len(nums)):
            if nums[right]:
                nums[left] = nums[right]
                left += 1
				
				# 从头到尾遍历完后，非0元素都按顺序跑到前面了，剩下的一定都是0
				# 因此第二次从left的位置开始，将末尾的元素全部赋值为0即可
        for i in range(left, len(nums)):
            nums[i] = 0

Python语法糖简单写法：

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        if len(nums) == 1:
            return

        left = 0
        for n in nums:
            if n != 0:
                nums[left] = n
                left += 1
        nums[left:] = [0] * (len(nums) - left)

2、一次遍历、直接交换

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        if len(nums) == 1:
            return

        left = 0
        for right in range(len(nums)):
            if nums[right]:
            	# 添加一层是否为0判断，避免自己与自己的无效交换
                if nums[left] == 0:
                    nums[left], nums[right] = nums[right], nums[left]
                left += 1

官方解答：

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        n = len(nums)
        left = right = 0
        while right < n:
            if nums[right] != 0:
                nums[left], nums[right] = nums[right], nums[left]
                left += 1
            right += 1

11、盛最多水的容器（中等）

题目描述

给定一个长度为 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⁴

题目思路

对于这道题，因为涉及到“容器”的左右边界，因此我们使用双指针从两侧向中间查找。

题目本质上是木桶原理的一个应用——也即容器盛水的最大容量由最短的那条边决定。

因此，当我们分别分别从左向右、从右向左遍历，容器盛水的量即为：

• min(height[left], height[right]) * (right - left)

并且，越往中间遍历，整个矩形的横边长度就越短，因此只有找到更高的木板——也就是height[i]更大的，才有可能找到能盛放更多水的“容器”。

算法代码

class Solution:
    def maxArea(self, height: List[int]) -> int:
                if len(height) < 2:
                    return 0

                max_area = 0
                left, right = 0, len(height) - 1
                while left < right:
                # 水的容器以左右最小值为准（木桶原理）
                    min_height = min(height[left], height[right])
                    max_area = max(min_height * (right - left), max_area)
                    # 从左向右找更高的木板
                    while left < right and height[left] <= min_height:
                        left += 1
                    # 同样，从右向左找更高的木板
                    while right > left and height[right] <= min_height:
                        right -= 1
                return max_area

15、三数之和（中等）

题目描述

给你一个整数数组 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⁵

题目思路

这道题题目名称为“三数之和”，和我们之前所做的“两数之和”非常类似，都是要求数组中存在数字之和等于目标值。
对于这道题，要求nums[i] + nums[j] + nums[k]=0，换个角度想，其实就是要求：

• -nums[k]=nums[i] + nums[j]
  • 这里，-nums[k]就是我们的target值；

因此，三数之和的问题就成功降维、转换为了两数之和的问题：

• 只要我们分别对每一个元素，寻找其数组中剩余元素是否存在之和等于其相反值的情况；
• 将所有情况汇总，即为最终结果：三数之和为0；

但与两数之和不同的是，一方面三数之和可能存在多个，并且答案要求不能重复；另一方面三数之和为0是存在很多特殊情况可以跳过。
因此直接套用TowSum哈希来判断是一种暴力搜索的策略。

这里，我们采取对数组进行排序、再使用双指针的办法来寻找答案。

首先我们需要明白，什么情况下三个数字之和为0？自然是：

• 负数 + 零（可能有）+正数

那么，当我们对数组完成从小到大的排序后，我们以此进行遍历（位置为i、数组长度为n）：

• 对于num[i]，我们将-num[i]作为target，并且定义两个指针left和right，分别从i+1的位置以及n-1分别从左到右、从右到左找TwoSum
  • 如果nums[left] + nums[right] == target，则说明正好找到了这样的三元组，直接加入到结果即可；
  • 如果两数之和大于target，说明需要和减小，因此右指针向左移动；
  • 如果两数之和小于target，说明需要和增大，因此左指针向右移动；

同时，也存在下面的跳出与去重策略：

• 如果数组长度小于3，那么肯定不存在这样的三元组，直接返回；
• 在遍历排序后的数组时，如果当前值已经大于0，后面的也一定都是比它大的，自然无论怎么加都会大于0，此时直接返回即可；
• 在遍历时，如果当前元素与上一个元素值相同，那么直接跳过避免重复；
• 对于找到元素后的重复规避：
  • 如果nums[left] == nums[left+1]，则left需要先加一跳过该元素；
  • 如果nums[right] == nums[right-1]，则right需要先减一跳过该元素；

算法代码

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        n = len(nums)
        if n < 3:
            return []

        three_num_res = []
        # 将数组按照递增排序
        nums.sort()
        for i in range(n):
            # 如果当前值已经大于0，那么后面的数字无论怎么加都会大于0，因此直接返回即可
            if nums[i] > 0:
                return three_num_res

            # 规避重复1：如果target已经检查过，则直接跳过
            if i > 0 and nums[i] == nums[i-1]:
                continue

            target, left, right = -nums[i], i + 1, n - 1
            while left < right:
                curr_two_sum = nums[left] + nums[right]
                if curr_two_sum == target:
                    three_num_res.append([nums[i], nums[left], nums[right]])
                    # 规避重复2：跳过满足条件的组合数字情况
                    while left < right and nums[left] == nums[left+1]:
                        left += 1
                    while left < right and nums[right] == nums[right-1]:
                        right -= 1
                    left += 1
                    right -= 1
                # 如果两数之和大于target，说明需要减小，因此右指针向左移动
                elif curr_two_sum > target:
                    right -= 1
                # 如果两数之和小于target，说明需要增大，因此左指针向右移动
                else:
                    left += 1

        return three_num_res

42、接雨水（困难）

题目描述

给定 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 * 10⁴
• 0 <= height[i] <= 10⁵

题目思路

这道题解法很多，包括动态规划等。
由于题目被划分到了双指针范畴，因此这里我们使用双指针法来解。

在双指针法的题目中也有一道类似的盛水题——11、盛最多水的容器。
这道题中比较简单，并且容器的边长体积不考虑，本质是一个比较直接的木桶问题。

对于这道接雨水的题目，则是需要考虑水池柱子自身体积，因此在积水量的计算上有所差别。

不过二者的相同点都在于——都是接水，因此水原则上总会从两边较矮的一侧流出去。

从题设的图片中我们可以看出，本身不管是柱子还是积水，都是以方块的形式存在的，因此在计算蓄水体积时，我们的思路是：

• 按槽位的进行判断与计算。
  • 需要注意，我们不要被“水流”所影响，每次我们只需要看当前i位置这一列的情况即可，尝试将每个槽位想像为一个水立方。

例如对于序列[2, 1, 3]，就是很明显在1处有一个凹槽，因此最大容纳的水量就是1。
同时，对于最左侧的柱子和最右侧的柱子，基于水的流动特性，我们应当始终从较矮的一侧开始遍历，这样可以保证另一侧（较高的）将水给拦住，不会流出去。

在分别从左到右、以及从右到左的遍历中，我们还需要分别记录左右两侧遍历过程中最高的墙柱：

• left_max
• right_max

记录该值的目的是为了计算从左向右或从右向左的过程中，对应i位置能需的水的最大值。

以从左向右为例（从右向左同理）：

• 首先，如果此时是从左向右来遍历观察，那么说明当前右侧的墙壁高度（height[right]）一定高于左边；
  • 这样就保证了当前位置是何种形状，右侧都能提供蓄水支撑；
• 其次，会判断i位置的柱子高度：
  • 如果高度比当前左侧的最大值小，那么说明左侧一定能够提供left_max高度的支撑；
  • 同时，右侧的高度也一定是大于等于左侧的left_max，否则就会变成右侧高度较矮、从右侧遍历了；
  • 最后，考虑带i位置自身的柱子高度，因此最终的蓄水体积就是： (left_max - height[i]) * 1；

最后，当left和right相遇时，就可以得到最终的结果了。

算法代码

class Solution:
    def trap(self, height: List[int]) -> int:
        trapped_rain = 0
        left, right = 0, len(height) - 1
        left_max, right_max = 0, 0
​
        while left < right:
            left_max = max(left_max, height[left])
            right_max = max(right_max, height[right])
            
            # 从较矮的一侧查看蓄水值，这样另一侧就可以默认提供更高的“空气墙”
            if height[left] < height[right]:
                trapped_rain += (left_max - height[left]) * 1
                left += 1
            else:
                trapped_rain += (right_max - height[right]) * 1
                right -= 1
        
        return trapped_rain

补充说明

所谓双指针解法，这里主要指的是针对列表的遍历定义两个不同的下标变量进行跟踪。
两个下标的移动方向既可以是通向的、也可以是相向的：

• 对于同向的移动，一般是二者的前进/暂停条件不同，通过这样的不同来做到满足题设体检的区间查找，从而进行求解；
  • 有点类似于快慢指针问题；
• 对于相向的移动，从上面的题目我们可以看出，一方面通过left与right之间的距离作为评估参数；另一方面也对nums[left]和nums[right]作为实际的计算与评估维度；