相向双指针

2026-01-13

1. 两数之和

给定一个非递减数组，从中找n个数，使之和为t
输入：[2,3,4,6,8]，t=9，n=2
输出（3,6）的索引：（2，4）
思路：双指针，两数之和大于t时，说明右边的大数找不到更小的数配对了，右边大数可删除。这样一个处理包含的信息量为O(N)

class Solution:
    def twoSum(self, numbers: List[int], target: int) - List[int]:
        left = 0
        right = len(numbers) - 1
        
        while left < right:
            sum = numbers[left] + numbers[right]
            if sum == target:
                return [left + 1, right + 1]
            if sum < target:
                left += 1
            else:
                right -= 1
        return [0,0]

2. 三数之和

给定一个数组，从中找出所有三元组满足和为t，重复三元组不算。

class Solution:
    def threeSum(self, nums: List[int]) - List[List[int]]:
        nums.sort()
        length=len(nums)
        res=[]
        for index in range(length-2):
            if sum([nums[index],nums[index+1],nums[index+2]])  0:
                break
            if sum([nums[index],nums[-1],nums[-2]]) < 0:
                continue
            if index0 and nums[index]==nums[index-1]:
                continue
            left = index+1
            right = length-1
            while left<right:
                if sum([nums[index],nums[left],nums[right]]) < 0:
                    left+=1
                elif sum([nums[index],nums[left],nums[right]])  0:
                    right-=1
                else:
                    res.append([nums[index],nums[left],nums[right]])
                    left+=1
                    while left<right and nums[left] == nums[left-1]:
                        left+=1
                    right -=1
                    while rightleft and nums[right] == nums[right+1]:
                        right -=1
        return res

3. 盛最多水的容器

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。返回容器可以储存的最大水量。

class Solution:
    def maxArea(self, height: List[int]) - int:
        l, r = 0, len(height)-1
        s_max = 0
        while l<r:
            s = (r-l)*min(height[l],height[r])
            s_max= s if s s_max else s_max
            if height[l] < height[r]:
                l+=1
            else:
                r-=1
        return s_max

4. 接雨水

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

class Solution:
    def trap(self, height: List[int]) - int:
        n = len(height)
        pre_max = height[:]
        suf_max = height[:]
        sum = 0
        for i in range(1,n):
            j = n-i-1
            pre_max[i] = max(height[i], pre_max[i-1])
            suf_max[j] = max(height[j], suf_max[j+1])
        for h,pre,suf in zip(height,pre_max,suf_max):
            sum += min(pre,suf)-h
        return sum

class Solution:
    def trap(self, height: List[int]) - int:
        n = len(height)
        pre_max = 0
        suf_max = 0
        sum = 0
        left = 0
        right = n-1
        while left< right:
            pre_max = max(pre_max, height[left])
            suf_max = max(suf_max, height[right])
            if pre_max<suf_max:
                sum += min(pre_max,suf_max) - height[left]
                left+=1
            else:
                sum += min(pre_max,suf_max) - height[right]
                right -= 1
        return sum

5. 长度最小的子数组

(209) 给定一个含有 n 个正整数的数组和一个正整数 target 。找出该数组中满足其总和大于等于 target 的长度最小的 子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。

思路：

暴力求解：遍历左端点或者右端点，以右端点为例。

# 第一次遍历以2为右端点
2 - 小于7，扩大
左边没有数了，无法扩大，说明以2为右端点无解，进行下一次迭代
    
# 第二次迭代，以3为右端点
3 - 小于7，扩大
2,3 - 小于7，扩大
左边没有数了，无法扩大，说明以3为右端点无解，进行下一次迭代
    
# 
1 - 小于7，扩大
3,1 - 小于7，扩大
2,3,1 - 小于7，扩大
无解
    
# 
2 - 小于7，扩大
1,2 - 小于7，扩大
3,1,2 - 小于7，扩大
2,3,1,2 - 大于7，说明以2为右端点，得到的解为4
    
#...

优化求解，利用都是正数的性质，还是遍历右端点

# 第一次遍历以2为右端点
2 - 小于7，扩大
左边没有数了，无法扩大，说明以2为右端点无解，进行下一次迭代
    
# 第二次迭代，以3为右端点
xxxxx 3 - 小于7，扩大
上一步迭代得到的全串为2，直接在此基础上向右扩展右端点
2,3 - 小于7，说明在第一次的全串(2)基础上扩展右端点(3)还是无法满足，进一步扩展右端点
2,3,1 - 小于7，说明在第一次的全串(2,3)基础上扩展右端点(1)还是无法满足，进一步扩展右端点
2,3,1,2 - 大于7，说明以2为右端点可以获得一个解，为了最短，尝试将左端点右移，发现3,1,2不满足，因此左端点不动，记录该长度为4，进一步扩展右端点
2,3,1,2,4 - 由于上一步的结果大于7，这次右端点扩展了一个数，肯定大于7，需要缩短（固定右端点）以找到最短序列，尝试右移左端点，
3,1,2,4 - 大于7，记录左边界更新（3），再次尝试右移左端点
1,2,4 - 大于等于7，记录该长度为3，更新最优解，记录左边界更新（1），再次尝试右移左端点
2,4 - 小于7，说明以4为右端点的情况已经遍历全了，回退一步：1，2，4，进一步扩展右端点
    
1，2，4，3 - 由于上一步的结果大于7，这次右端点扩展了一个数，肯定大于7，需要缩短（固定右端点）以找到最短序列
2，4，3 - 大于等于7，记录该长度为3，更新最优解，记录左边界更新（2），再次缩短
4，3 - 大于等于7，记录该长度为2，更新最优解，记录左边界更新（4），再次缩短
3 - 小于7，说明以3为右端点的情况已经遍历全了，回退一步：3，4，进一步扩展右端点
    
# 遍历完成

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) - int:
        n = len(nums)
        res = n+1
        sum = 0
        left = 0
        for right,x in enumerate(nums):
            sum += x
            while sum - nums[left] = target:
                sum  -= nums[left]
                left += 1                 
            res = min(res, right-left+1) if sum = target else res
           
        return res if res <=n else 0