02-双指针

总结

题目总结

1-283-移动零到末尾

题目：把数组0移动到末尾
思路1：快慢指针找非0，交换到前面
- 快指针：存放下一个非0元素；慢指针：存放下一个可放置的位置
思路2：仍然快慢指针
- 前面先存非0，不做交换，后面再统一补0

2-011-盛最多水的容器

题目

给高度height数组，找出2个位置，使其面积最大，输出面积。

左右指针中间靠拢法

面积公式，左右指针往中间靠拢，谁低 谁往中间靠，再算新面积 $area = \underset{长度}{\underset{⏟}{(j - i)}} * \underset{高度}{\underset{⏟}{min (h_{i}, h_{j})}}$

015-三数之和

题目

给nums数组，求取满足3个数和为0的所有不同三元组。

排序遍历+双指针找两数和

排序遍历，使用双指针找两数求和，有重复，不能使用hash补数
nums[i] 头数过滤：等于nums[i-1]，已处理过；已超过三数和，跳过；
双指针两数和内部过滤：最难最核心
- 找到1对l-r后，不可仅+1,-1，要据数字重复，一直往中间靠拢

4-100-接雨水

题目

给定若干柱子height数组，求问最多能接多少雨水。

核心公式

每根柱子接水量，取决于左边最高柱子和右边最高柱子的较低值，减去当前高度 ${水层高度}_{i} = min (max_left, max_right) - height [i]$

暴力法

每个柱子去遍历求解

双指针法

维护左右2个指针和左右2个max值
根据left_max和right_max 谁更小，计算l或r柱子的接水量

DP法

DP 计算各位置左右最大值
再依次求解每根柱子接水量

题目

1-283-移动零到末尾

leetcode-283

输入：nums数组，包含许多0
输出：nums数组，把所有0移动到末尾，保证其他数字相对有序
示例：
- [0, 1, 0, 3, 12] -> [1, 3, 12, 0, 0]

快慢指针找非0交换到前面

慢指针：指向，下一个存放非0元素的位置
快指针：往后找非0元素，找到非0元素
- fast和slow交换，slow往前移动1格
所有的非0交换到前面，自然，所有的0就在末尾

python

def moveZeroes_exchange(self, nums: List[int]) -> None:
    """快指针，找到非0元素，一直往前面交换，所有的非0都在前面后，自然0就在末尾
    """
    if not nums:
        return nums

    # fast找下一个非0元素，slow指向下一个非0元素存储的位置
    slow = fast = 0

    while fast < len(nums):
        if nums[fast] != 0:  
            # 找到非0元素，非0元素往前放，做交换
            nums[fast], nums[slow] = nums[slow], nums[fast]  
            slow += 1
        fast += 1
  return nums

前面先存非0后面再统一补0

快慢指针
- 快指针：找下一个非0元素
- 慢指针：存储下一个非0元素要存的位置
不做交换
- 前面直接存储非0，后面从slow开始，统一赋值0

python

def moveZeroes_noexchange(self, nums: List[int]) -> None:
    """快慢指针，前面统一存非0，后面统一赋0
    """
    if not nums:
        return nums
    # slow指向下一个可以存储的位置，fast找下一个非0元素
    slow = fast = 0
    while fast < len(nums):
        # 找到非0元素
        if nums[fast] != 0:
            nums[slow] = nums[fast]
            slow += 1
        fast += 1
    # 后面空缺，统一赋0
    for i in range(slow, len(nums)):
        nums[i] = 0
    return nums

2-011-盛最多水的容器

leetcode-011

输入：给一个高度数组 height []。在第一象限里，对应x轴上有多条线。
输出：找出左右2个高度，使构成的容器 盛水最多，输出面积。

面积计算

从左到右，i和j 2条线，高度分别为 height[i], height[j]，二者面积计算如下 $area = \underset{长度}{\underset{⏟}{(j - i)}} * \underset{高度}{\underset{⏟}{min (h_{i}, h_{j})}}$

左右指针往中间靠

双指针i和j，从两边，分别向中间靠拢
- 指针i：从0开始，在左边，往中间靠
- 指针j：从n-1开始，在右边，往中间靠
循环，计算i和j的面积，更新最大面积。
往中间靠，迭代：
- i和j的高度，谁低 谁往中间靠，再去计算新的面积

python

def maxArea(self, height: List[int]) -> int:
    if not height or len(height) <= 1:
        return 0
  
    # 双指针，从左右往中间考虑
    i = 0
    j = len(height) - 1

    max_area = 0
    while i < j:
        # 计算当前面积
        area = (j - i) * min(height[j], height[i])  

        # 更新最大面积
        max_area = max(area, max_area)

        # 往中间考虑，i和j的高度，谁小，谁往中间靠
        if height[i] < height[j]:  
            i += 1
        else:
            j -= 1
    return max_area

3-015-三数之和

leetcode-015

输入：数组nums
输出：满足三个数求和为0的所有三元组。和可以为target。

错误：排序遍历使用Hash补数找两数求和

排序遍历+Hash找补数错误思想

核心思路

先对数组做从小到大排序
从前往后遍历，固定nums[i]，在i后面，使用双指针补数法找2数之和
- 如果nums[i] > target：不满足条件，跳过，后面的数只会比nums[i]更大。
- 如果nums[i] == nums[i-1]：和上一个数重复，跳过。
- 计算剩余2数之和：sum = target - nums[i]
- 使用Hash补数方法：在[i+1, n-1]区间，找到和为sum的两个数。两数之和

Hash无法处理数字重复导致错误

Case：[0, 0, 0, 0]
当固定nums[i]后，在[0, 0, 0] 中使用hash补数，找两个数和为0
- 由于hash无法存储 2个数值相同但位置不同的数，只能对一个0存储位置，
- 导致会重复或漏掉

python

def threeSum_hash(self, nums: List[int]) -> List[List[int]]:
    res = []

    if not nums or len(nums) < 3:
        return res

    # 1. 从小到大排序
    nums.sort() 
    three_sum_value = 0
    n = len(nums)

    # 2. 遍历每个nums[i]，在i后面找2个数，使得和为three_sum
    for i in range(n-2):

        # 3. 过滤条件
        if nums[i] > three_sum_value:
            # 当前数，已经超过目标和，未来的数比当前数更大
            continue

        if i > 0 and nums[i] == nums[i-1]:
            # 和上一个数已重复，去掉
            continue

        # 4. 在[i+1, n-1] 使用hash补数法，找到2个数
        two_sum_value = three_sum_value - nums[i]
        num2pos = {}  
        for j in range(i+1, n):
         		 # 可能有0 0 0 这样的case，使用hash则不能凑出相同数字位置不同的数
            # 计算两数之和的补数
            complement = two_sum_value - nums[j]
            if complement in num2pos:
                # 找到目标数字
                res.append((nums[i], nums[j], complement))
            else:
                num2pos[nums[j]] = j
    return res

排序遍历使用左右指针找两数求和

排序遍历+左右指针找两数和核心思路

先对nums做从小到大排序
固定nums[i]，在[i+1, n-1]区间，找2个数，利用两数求和 = target-nums[i]。
但由于有重复，两数求和，不能使用hash补数，只能使用双指针。类似盛水。

过滤策略

nums[i] 头数过滤：等于nums[i-1]，已经处理过了；已超过三数和，跳过
双指针内部过滤：非常重点
- 再找到一对l和r后，不能仅做 l+=1, r-=1
- l和r指针，要根据数字重复，一直往中间靠拢
- 这是这道题的最难最核心之处了

python

def threeSum_sort_two_pointer(self, nums: List[int]) -> List[List[int]]:
    res = []
    if not nums or len(nums) < 3:
        return res

    three_sum_value = 0

    # 1. 先对nums做排序
    nums.sort()  
    n = len(nums)

    # 2. 遍历固定nums[i]，依次在后面找2个数，使其求和为two_sum
    for i in range(n-2):  

        # 3. 过滤条件
        # 由于从小到大排列，当前nums[i] 已经超过三数之和，则不用做循环了
        if nums[i] > three_sum_value:
            continue

        # 和上一个头数，相同，也过滤
        if i > 0 and nums[i] == nums[i-1]:
            continue

        two_sum_value = three_sum_value - nums[i]  

        # 4. 使用双指针，求解two_sum，不能使用hash，hash无法处理数字相同的问题，会遗漏或无法过滤
        l, r = i+1, n-1
        while l < r:
            current_sum = nums[l] + nums[r]
            if current_sum == two_sum_value:  
                # 找到一组解
                res.append([nums[i], nums[l], nums[r]])

                # 不能只往中间靠1步，因为可能有重复，需要过滤，比如0000
                l += 1
                r -= 1

                # l 往左走，找到直到不同的数字
                while l < r and nums[l] == nums[l+1]:  
                    l += 1

                # r 往右走，直到找到不同的数字
                while l < r and nums[r] == nums[r-1]:  
                    r -= 1

            elif current_sum < two_sum_value:
                l += 1
            else:
                r -= 1

    return res

4-100-接雨水

leetcode-100，类似盛水容器

输入：n个柱子，height 高度数组，宽度为1。
输出：下雨，整体所有柱子加起来， 能接满多少水

接水核心: 木桶效应

每根柱子 接水量：取决于左边最高柱子和右边最高柱子的较小值，减去本柱子高度。
- 接水条件：最小值 > 本柱子高度
${水层高度}_{i} = min (max_left, max_right) - height [i]$
最左边、最右边的柱子无法接水。
柱子宽度为1，可忽略。

暴力法：每根柱子接水量求和

暴力法每根柱子接水量求和

核心思想

求出每根柱子 接水量，再累加即为所有柱子接水量。
每根柱子接水量：左右两边最高柱子 取其小 - 当前柱子高度
但是会超时。322 / 324 通过率

暴力步骤

遍历求解每一根柱子的接水量，再累加即可。首尾柱子不能接水
- 求解左右两边最高柱子的较小值
- 计算当前柱子的接水量： min(max_l_height, max_r_height) - height[i]
- res累加求和，即为整体接水量

python

def trap_force_loop(self, height: List[int]) -> int:
    """
    每根柱子的接水量：取决于左边最高柱子、右边最高柱子的较小值，减去当前的高度
    暴力求解
    """
    if not height or len(height) < 3:
        return 0

    # 最终整体接水量
    res = 0
    n = len(height)

    # 1. 遍历求解每一根柱子的接水量，首尾柱子不能接水
    for i in range(1, n-1): 
      
        # 2. 求解左右两边最高柱子的较小值
        max_l_height = max(height[0:i])
        max_r_height = max(height[i+1:])
        min_height = min(max_l_height, max_r_height)  

        # 3. 计算当前柱子的接水量
        if min_height > height[i]:
            res += min_height - height[i]  
    return res

左右指针法：依次求解每根柱子接水量

核心思想

不用每次 都从头计算 左右2边最高柱子。
左右柱子指针：从左右两边向中间靠拢，依次计算 左右柱子的接水量
维护left_max和right_max：代表左右柱子 高度最高值
- left_max < right_max：可计算l位置的接水量
- right_max <= left_max ：可计算r位置的接水量

python

def trap_left_right_pointer(self, height: List[int]) -> int:
    """
    每根柱子接水量，取决于左边最高柱子、右边最高柱子的较小值，减去当前高度
    维护左右2个指针，左右2边最高值，依次计算left或right位置的接水量
    """
    if not height or len(height) < 3:
        return 0

    res = 0
    n = len(height)

    # 左右指针
    l, r = 1, n - 2
    # 左右目前的最高度，最左和最右都不能接水
    left_max, right_max = height[0], height[n-1]

    while l <= r:

        if left_max < right_max:  
            # 左侧比右侧更低，可计算位置l的接水量
            if left_max > height[l]:
                res += left_max - height[l]  
            else:
                left_max = height[l]
            l += 1
        else:
            # 右侧比左侧低，可计算r位置的接水量
            if right_max > height[r]:
                res += right_max - height[r]  
            else:
                right_max = height[r]
            r -= 1
    return res

DP计算最大值：再依次求解每根柱子接水量

DP计算最大值再依次求解

先DP计算出，每个位置的左侧最高柱子、右侧最高柱子
- lmaxs[i] = max(lmaxs[i-1], height[i-1])
- rmaxs[i] = max(rmaxs[i+1], height[i+1])
再依次计算出每个位置的接水量即可

python

def trap_dpmax(self, height: List[int]) -> int:
    """
    每根柱子接水量，取决于左边最高柱子、右边最高柱子的较小值，减去当前高度
    先DP求解出，每个位置的左边最高住址和右边最高柱子
    """
    if not height or len(height) < 3:
        return 0

    n = len(height)
    res = 0

    # 1. dp 计算出每个位置左边、右边的最高值
    lmaxs = [0] * n 
    rmaxs = [0] * n

    # 从左到右，计算lmax
    for i in range(1, n):
        lmaxs[i] = max(lmaxs[i-1], height[i-1])  

    # 从右到左，计算rmax
    for i in range(n-2, -1, -1):
        rmaxs[i] = max(rmaxs[i+1], height[i+1])  

    # 2. 遍历计算出每个位置的接水量，首尾位置不接水
    for i in range(1, n-1):
        min_height = min(lmaxs[i], rmaxs[i])
        if min_height > height[i]:
            res += min_height - height[i]  

    return res

总结 ​

题目总结 ​

题目 ​

1-283-移动零到末尾 ​

快慢指针找非0交换到前面 ​

前面先存非0后面再统一补0 ​

2-011-盛最多水的容器 ​

左右指针往中间靠 ​

3-015-三数之和 ​

错误：排序遍历使用Hash补数找两数求和 ​

排序遍历使用左右指针找两数求和 ​

4-100-接雨水 ​

暴力法：每根柱子接水量求和 ​

左右指针法：依次求解每根柱子接水量 ​

DP计算最大值：再依次求解每根柱子接水量 ​

总结

题目总结

题目

1-283-移动零到末尾

快慢指针找非0交换到前面

前面先存非0后面再统一补0

2-011-盛最多水的容器

左右指针往中间靠

3-015-三数之和

错误：排序遍历使用Hash补数找两数求和

排序遍历使用左右指针找两数求和

4-100-接雨水

暴力法：每根柱子接水量求和

左右指针法：依次求解每根柱子接水量

DP计算最大值：再依次求解每根柱子接水量