相向双指针

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 index>0 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 right>left 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，进一步扩展右端点

# 遍历完成

```python
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

赏

谢谢你请我吃糖果