2020-06-28

针对209 长度最小的子数组

第一个版本，前缀和，加上双指针。

class Solution:
    def minSubArrayLen(self, s: int, nums: List[int]) -> int:
        if not nums:return 0
        if max(nums)>=s:return 1  #针对单个大值
        dp=[0]
        k=len(nums)
        now=0
        for i in range(k):
            now += nums[i]
            dp.append(now)  #dp 前缀和准备完毕
        if now<s:return 0   #总和不足
        diff=k+2  #大值，这是跨度
        slow=fast=0
        for slow in range(k+1):
            while fast<=k and dp[fast] - dp[slow]<s:
                fast += 1
            if fast == k+1: #从此slow到最后，也不够了，停下。
                break
            elif dp[fast] - dp[slow]>=s: #update
                t=fast-slow
                if t==1:  #多余
                    return 1
                if t<diff:
                    diff=t
        return diff

version 2
随着指针挪动，更新前缀和，max 和sum 都压缩在循环中

class Solution:
    def minSubArrayLen(self, s: int, nums: List[int]) -> int:
        if not nums:return 0
        k=len(nums)
        diff=k<<1
        aa=bb=slow=fast=0
        nums.append(0)  #利用负数索引
        for slow in range(k+1):
            if nums[slow-1]>=s:return 1  #单个大值
            aa += nums[slow-1]  #负数索引用上了
            while fast<=k and bb-aa<s:  #前缀和的差
                fast += 1
                bb += nums[fast-1]
            if fast == k+1:
                if bb<s:return 0   #bb==sum(nums)
                break
            elif bb-aa>=s:diff=min(diff,fast-slow)  #update
        return diff

version 3 ，copy,维护区间和

class Solution:
    def minSubArrayLen(self, s: int, nums: List[int]) -> int:
        if not nums:return 0
     
        n = len(nums)
        ans = n + 1
        start, end ,total = 0, 0, 0 
        while end < n:
            total += nums[end]
            while total >= s:
                ans = min(ans, end - start + 1)
                total -= nums[start]
                start += 1
            end += 1
        
        return 0 if ans == n + 1 else ans

优化的过程，
1、边界值，特殊处理
2、单调递减变量的初值设定
3、双指针，for 和while 配合

version 4

class Solution:
    def minSubArrayLen(self, s: int, nums: List[int]) -> int:
        if not nums:return 0
        
        n = len(nums)
        ans = n ##
        start, end, total = 0, 0, 0
        for end in range(n):
            total += nums[end]
            while total >= s:
                ans = min(ans, end - start) ##
                total -= nums[start]
                start += 1            
        
        return 0 if ans == n else ans+1 ##