Skip to content

Latest commit

 

History

History
527 lines (365 loc) · 14.5 KB

专题-双指针(滑动窗口).md

File metadata and controls

527 lines (365 loc) · 14.5 KB

Index

三数之和 (LeetCode, Medium, No.0015, 2021-10)

双指针(首尾)

问题简述 
给定一个数组，找出该数组中所有和为 0 的三元组。
思路
  • 排序后，问题可以简化成两数之和（LeetCode-167）；
  • 先固定一个数，然后利用首尾双指针进行对向遍历；
  • 注意跳过相同结果；
题目描述 
给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。

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

示例 1：
    输入：nums = [-1,0,1,2,-1,-4]
    输出：[[-1,-1,2],[-1,0,1]]

示例 2：
    输入：nums = []
    输出：[]

示例 3：
    输入：nums = [0]
    输出：[]

提示：
    0 <= nums.length <= 3000
    -10^5 <= nums[i] <= 10^5

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/3sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
Python 
from typing import List

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

        # 设置目标值
        target = 0
        # 排序
        nums = sorted(nums)

        for i in range(L - 2):  # 固定第一个数
            # 剪枝
            if i > 0 and nums[i] == nums[i - 1]: continue
            if nums[i] + nums[i + 1] + nums[i + 2] > target: break
            if nums[i] + nums[L - 2] + nums[L - 1] < target: continue

            # 设置左右指针
            l, r = i + 1, L - 1
            while l < r:

                s = nums[i] + nums[l] + nums[r]
                if s < target:
                    l += 1
                elif s > target:
                    r -= 1
                else:  # s == target
                    ret.append([nums[i], nums[l], nums[r]])

                    # 同时移动双指针
                    l += 1
                    r -= 1

                    # 如果跟上一个值相同，就跳过
                    while l < r and nums[l] == nums[l - 1]: l += 1
                    while l < r and nums[r] == nums[r + 1]: r -= 1

        return ret

两数之和2(输入有序数组) (LeetCode, Easy, No.0167, 2021-10)

双指针(首尾)

问题简述 
找出一个非递减数组中和等于 target 的两个数字，输出它们的下标。

假定题目一定有一个解。
思路
  • 有序数组搜索，考虑首尾双指针，对向遍历；
题目描述 
给定一个已按照 非递减顺序排列 的整数数组 numbers ，请你从数组中找出两个数满足相加之和等于目标数 target 。

函数应该以长度为 2 的整数数组的形式返回这两个数的下标值。numbers 的下标 从 1 开始计数 ，所以答案数组应当满足 1 <= answer[0] < answer[1] <= numbers.length 。

你可以假设每个输入 只对应唯一的答案 ，而且你 不可以 重复使用相同的元素。

 
示例 1：
    输入：numbers = [2,7,11,15], target = 9
    输出：[1,2]
    解释：2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。
示例 2：
    输入：numbers = [2,3,4], target = 6
    输出：[1,3]
示例 3：
    输入：numbers = [-1,0], target = -1
    输出：[1,2]


提示：
    2 <= numbers.length <= 3 * 10^4
    -1000 <= numbers[i] <= 1000
    numbers 按 非递减顺序 排列
    -1000 <= target <= 1000
    仅存在一个有效答案

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/two-sum-ii-input-array-is-sorted
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
Python 
class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        """"""
        lo, hi = 0, len(numbers) - 1

        while lo < hi:
            tmp = numbers[lo] + numbers[hi]

            if tmp < target:
                lo += 1
            elif tmp > target:
                hi -= 1
            else:
                return [lo + 1, hi + 1]

接雨水 (LeetCode, Hard, No.0042, 2021-10)

双指针(首尾)

问题简述 
给定 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 个单位的雨水（蓝色部分表示雨水）。 

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/trapping-rain-water
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
思路1：双指针(Python) 
class Solution:
    def trap(self, height: List[int]) -> int:
        """"""
        l, r = 0, len(height) - 1
        
        ans = 0
        max_l = max_r = 0  # 保存当前位置时，左右最高的柱子
        
        while l <= r:
            if height[l] <= height[r]:
                if height[l] > max_l:
                    max_l = height[l]
                else:
                    ans += max_l - height[l]
                l += 1
            else:
                if height[r] > max_r:
                    max_r = height[r]
                else:
                    ans += max_r - height[r]
                r -= 1
                
        return ans
思路2：左右遍历两次(C++) 
class Solution {
public:
    int trap(vector<int>& H) {
        int n = H.size();
        
        vector<int> l_max(H);
        vector<int> r_max(H);
        
        for(int i=1; i<n; i++)
            l_max[i] = max(l_max[i-1], l_max[i]);
        
        for(int i=n-2; i>=0; i--)
            r_max[i] = max(r_max[i+1], r_max[i]);
        
        int ret = 0;
        for (int i=1; i<n-1; i++)
            ret += min(l_max[i], r_max[i]) - H[i];
        
        return ret;
    }
};

最接近的三数之和 (LeetCode, Medium, No.0016, 2021-10)

双指针(首尾)

问题简述 
给定一个数组，找出该数组中和最接近指定值的三元组。
思路
  • 思路跟三数之和基本一致；
  • 当找到比当前更接近的结果时更新；
题目描述 
给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。

示例：
    输入：nums = [-1,2,1,-4], target = 1
    输出：2
    解释：与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。

提示：
    3 <= nums.length <= 10^3
    -10^3 <= nums[i] <= 10^3
    -10^4 <= target <= 10^4

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/3sum-closest
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
Python 
from typing import List

class Solution:
    def threeSumClosest(self, nums: List[int], target: int) -> int:
        """"""
        nums = sorted(nums)

        L = len(nums)
        ret = nums[0] + nums[1] + nums[2]  # 初始化，len(nums) >= 3
        for i in range(L - 2):

            # 跳过重复元素
            if i > 0 and nums[i] == nums[i - 1]:
                continue

            # 利用单调性剪纸
            min_s = nums[i] + nums[i + 1] + nums[i + 2]  # 最小和
            if min_s > target:
                if abs(min_s - target) < abs(ret - target):
                    ret = min_s
                break

            max_s = nums[i] + nums[L - 2] + nums[L - 1]  # 最大和
            if max_s < target:
                ret = max_s
                continue

            # 初始化双指针
            l, r = i + 1, L - 1
            while l < r:
                s = nums[i] + nums[l] + nums[r]
                if abs(s - target) < abs(ret - target):
                    ret = s

                if s < target:
                    l += 1
                    while l < r and nums[l] == nums[l - 1]: l += 1
                elif s > target:
                    r -= 1
                    while l < r and nums[r] == nums[r + 1]: r -= 1
                else:  # ret == target
                    return ret
        return ret
利用单调性剪枝

  • 在经过排序后，每轮迭代时，三数之和的最大值和最小值是确定的；

  • 所以如果最小值比目标值大，那么后面无论怎么移动双指针，差值都只会越来越大；最大值比目标值小时同理；

  • 代码细节：

    # 剪枝：利用单调性
min_s = nums[i] + nums[i + 1] + nums[i + 2]  # 最小和
if min_s > target:  # 如果最小和也大于 target，则剩余部分的差值肯定越来越大
    # 容易忽略的一步，注意此时也是有可能出现答案的，比如 ret < 0 < min_s 时
    if abs(min_s - target) < abs(ret - target):
        ret = min_s
    break

max_s = nums[i] + nums[L - 2] + nums[L - 1]  # 最大和
if max_s < target:  # 如果最大和也小于 target，则剩余部分的差值肯定越来越大
    ret = max_s  # 此时 ret < max_s < target，所以 max_s 必然比当前 ret 更接近目标值
    continue

有效三角形的个数 (LeetCode, Medium, No.0611, 2021-10)

双指针(首尾)

问题简述 
给定一个包含非负整数的数组，你的任务是统计其中可以组成三角形三条边的三元组个数。
思路
  • 排序 + 首尾双指针；
  • 相当于计算两数之和大于目标值的个数；
题目描述 
给定一个包含非负整数的数组，你的任务是统计其中可以组成三角形三条边的三元组个数。

示例 1:
    输入: [2,2,3,4]
    输出: 3
    解释:
    有效的组合是: 
    2,3,4 (使用第一个 2)
    2,3,4 (使用第二个 2)
    2,2,3
注意:
    数组长度不超过1000。
    数组里整数的范围为 [0, 1000]。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/valid-triangle-number
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
Python 
class Solution:
    def triangleNumber(self, nums: List[int]) -> int:
        """"""
        nums = sorted(nums)
        
        cnt = 0
        for i in range(2, len(nums)):  # 注意：循环区间
            
            lo, hi = 0, i - 1
            while lo < hi:
                s = A[lo] + A[hi]
                
                if s > A[i]:
                    cnt += hi - lo  # 范围剪枝
                    hi -= 1
                else:
                    lo += 1
                    
        return cnt

盛最多水的容器 (LeetCode, Medium, No.0011, 2021-10)

双指针(首尾)

问题简述 
给你 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0) 。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

说明：不能倾斜容器。

示例 1：
    输入：[1,8,6,2,5,4,8,3,7]
    输出：49 
    解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/container-with-most-water
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
思路
  • 首尾双指针遍历
Python 
class Solution:
    def maxArea(self, height: List[int]) -> int:
        """"""
        l, r = 0, len(height) - 1
        ret = (r - l) * min(height[l], height[r])  # 初始化

        while l < r:
            if height[l] < height[r]:
                l += 1
            else:
                r -= 1
            
            tmp = (r - l) * min(height[l], height[r])
            ret = max(ret, tmp)
            
        return ret