209. 长度最小的子数组

发表于 更新于 分类于
这是文章开头，显示在主页面，详情请点击此处。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        # 1、二分法 分长度，再暴力比较每种长度的和 是否满足条件。耗时较长O(n log n) 时间复杂度。
        # n = len(nums) 
        # left = 1
        # right = n
        # def build_arraysum_list(interval :int):
        #     result = []
        #     temp = 0
        #     # python 的切片操作太慢了！！！ 算法题中不能这样简写！！！
        #     # result += [ sum(nums[i:i+interval]) for i in range(0,n-interval+1,1)]
        #     # return max(result)  
        #     for i in range(0,n-interval+1,1):
        #         sum_temp = 0
        #         for ii in range(i,i+interval):
        #             sum_temp += nums[ii]
        #         # sum_temp = sum(nums[i:i+interval]) python 的切片操作太慢了！！！ 
        #         while temp<sum_temp:
        #             temp = sum_temp
        #     return temp
        # def search_II(left,right):
        #     while left<=right:
        #         mid = (left+right)>>1
        #         sum_ele = build_arraysum_list(mid)
        #         if sum_ele >= target:
        #             return search_II(left,mid-1)
        #         else:
        #             return search_II(mid+1,right)
        #     return left if left<=n else 0
        # return search_II(left,right)

        # # 2、滑动窗口方法，确定终止指针，根据条件移动起始指针，O(n) 时间复杂度。
        i = 0
        n = len(nums)
        windows_length = n
        sum_windows = 0
        for j in range(n):
            # sum_windows = sum(nums[i:j+1]) python切片操作太慢！！！
            sum_windows += nums[j]
            while sum_windows >= target:
                # 窗口满足条件，记录数据，并移动起始位置。
                windows_length = min(j-i+1,windows_length)
                sum_windows -= nums[i]
                i += 1 
        return windows_length if sum(nums)>=target else 0