leetcode双指针题目总结

283. 移动零

题目描述

给定一个数组 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

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

解题

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        ts = 0
        for i in range(len(nums)):
            if nums[i] != 0:
                nums[ts] = nums[i]
                ts += 1

        for i in range(ts, len(nums)):
            nums[i] = 0
        return nums

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 <= 105
• 0 <= height[i] <= 104

解法

我们可以使用双指针（一个从列表的开头、一个从末尾）来找到最大面积。每次根据当前的两个指针对应的高度计算面积，然后移动较短的指针向内靠拢。移动较短的指针是因为面积取决于最短的高度，因此移动较短的指针才有可能增加面积。

class Solution:
    def maxArea(self, height: List[int]) -> int:
        left =0
        right = len(height) - 1
        max_area = 0

        while left < right:
            current_area = (right-left) * min(height[left],height[right])
            max_area = max(max_area, current_area)

            if height[left] < height[right]:
                left += 1
            else:
                right -= 1

        return max_area

解释

• left 和 right 分别是双指针，初始时分别指向列表的两端。
• 每次计算当前指针对应的面积并更新 max_area。
• 选择高度较小的指针向内移动，以尝试获得更大的面积。
• 循环终止时，max_area 就是最大面积。

时间复杂度

该算法的时间复杂度为 O(n)，因为每次只移动一个指针。

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
• -105 <= nums[i] <= 105

解法

思路

使用 排序 + 双指针法 来降低时间复杂度，步骤如下：

1. 排序数组：先对 nums 进行排序，以方便使用双指针。

2. 遍历数组，固定一个元素：使用一个循环来固定第一个元素 nums[i]，并跳过重复的元素以避免重复解。

3. 双指针寻找匹配的三元组

   • 使用两个指针 left 和 right，分别指向 i+1 和数组的最后一个元素。

   • 计算三个数的和

     sum = nums[i] + nums[left] + nums[right]
     

     • 如果 sum == 0，则找到一个三元组，将其加入结果。
     • 如果 sum < 0，说明和太小，移动 left 指针以增大和。
     • 如果 sum > 0，说明和太大，移动 right 指针以减小和。

   • 移动指针时，跳过重复元素以避免重复解。

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums = sorted(nums)
        lis = []
        for i in range(len(nums)):
            if i > 0 and nums[i] == nums[i-1]:
                continue

            left, right = i+1, len(nums) - 1
            while left < right:
                total = nums[i] + nums[left] + nums[right]
                if total == 0:
                    lis.append([nums[i], nums[left], nums[right]])
                    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
                elif total < 0:
                    left += 1
                else:
                    right -= 1

        return lis

解释

• 排序后的数组方便使用双指针，并且可以通过跳过相邻相同的元素来避免重复三元组。
• 外部循环固定第一个元素，双指针在剩下的部分查找符合条件的三元组。
• 总时间复杂度为 O((n^2)，比原方法更高效。

优势

这种方法通过减少嵌套循环，提高了效率，适合处理较大的输入。

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 * 104
• 0 <= height[i] <= 105

解答

具体思路

假设这些柱子之间会积水，那么每根柱子上能积多少水，取决于它左边和右边最高的柱子。这是因为水会被高的柱子“挡住”，从而在矮的柱子处积水。

1. 双指针法：
   • 我们用两个指针 left 和 right，分别从数组的两端（左边和右边）开始。
   • left 从左往右移动，right 从右往左移动。
2. 维护两个变量来记录两侧的最高柱子：
   • left_max：记录从左侧到当前 left 指针位置的最高柱子高度。
   • right_max：记录从右侧到当前 right 指针位置的最高柱子高度。
3. 积水量的计算逻辑：
   • 每根柱子积水的量取决于它左边和右边的最高柱子，因为水只会停留在比它高的柱子之间。
   • 如果 left_max比 right_max 矮，则意味着：
     • 左边柱子高度小，左边的 left_max 是决定 left 柱子能否积水的因素。
     • 如果 left_max 高于 height[left]，则 height[left] 可以积水 left_max - height[left] 的量。
     • 否则，我们更新 left_max。
     • 然后 left 指针右移一格，继续这个过程。
   • 如果 right_max小于等于 left_max，那么 right柱子能否积水，取决于 right_max
     • 如果 right_max 大于 height[right]，则 height[right] 可以积水 right_max - height[right] 的量。
     • 否则，我们更新 right_max。
     • 然后 right 指针左移一格，继续这个过程。
4. 终止条件：
   • 当 left 和 right 相遇时，整个遍历结束，此时计算出的 water_trapped 就是所有积水量的总和。

class Solution:
    def trap(self, height: List[int]) -> int:
        left = 0
        right = len(height) - 1
        left_max = 0
        right_max = 0
        water_set = 0

        while left < right:
            if height[left] < height[right]:
                if height[left] >= left_max:
                    left_max = height[left]
                else:
                    water_set += left_max - height[left]
                left += 1
            else:
                if height[right] >= right_max:
                    right_max = height[right]
                else:
                    water_set += right_max - height[right]
                right -= 1
        return water_set

x - height[left]
left += 1
else:
if height[right] >= right_max:
right_max = height[right]
else:
water_set += right_max - height[right]
right -= 1
return water_set