每日一题——leecode209（ 长度最小的子数组）

题意

难度：中等

给定一个含有 n 个正整数的数组和一个正整数 target 。

找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

示例 1：

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

示例 2：

1
2
输入：target = 4, nums = [1,4,4]
输出：1

示例 3：

1
2
输入：target = 11, nums = [1,1,1,1,1,1,1,1]
输出：0

思考

首先你要了解一下float(‘inf’)正负无穷：float(“inf”)是什么？_狂奔的菜鸡的博客-CSDN博客_float inf

一般就用在数组或者字符串上，我们先从字面上来认识一下滑动窗口：

滑动：窗口可以按照一定的方向移动。
窗口：窗口大小可以固定，也可以不固定，此时可以向外或者向内，扩容或者缩小窗口直至满足条件。

解题步骤：

  • 使用左右指针 left 和 right，left 和 right 之间的长度即为滑动窗口的大小（即连续数组的大小）。
  • 如果滑动窗口内的值 sum >= target，维护连续数组最短长度，left 向右移动，缩小滑动窗口。
  • 如果滑动窗口内的值 sum < target，则 right 向有移动，扩大滑动窗口。

我的解法（直男思维）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def minSubArrayLen(self, s: int, nums: List[int]) -> int:
        lowsum=0
        for i in range(0,len(nums)):
            lowsum+=nums[i]
        if lowsum<s:
            return 0        
        #滑动窗格解法
        left=0
        right=0
        min_len=float('inf')
        sum=0
        while right<len(nums):
            sum+=nums[right]
            while sum >= s:
                min_len=min(min_len,right-left+1)
                sum-=nums[left]
                left+=1
            right+=1
        return min_len

官方代码（精致的小女孩）：

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
class Solution:
    def minSubArrayLen(self, s: int, nums: List[int]) -> int:
        if not nums:
            return 0
        n = len(nums)
        # 滑动窗口左右边界
        left = right = 0
        # 记录当前元素和
        sum = 0
        # 记录最短长度
        min_len = float('inf')
        while right < n:
            sum += nums[right]
            # 如果当前元素和 >= s
            while sum >= s:
                # 取之前窗口长度和当前窗口长度最短的
                min_len = min(min_len, right - left + 1)
                # 去掉左侧的数
                sum -= nums[left]
                # 缩小窗口
                left += 1
            right += 1

        # 如果整个数组所有元素的和相加都 < s
        # 即不存在符合条件的子数组，返回 0
        if min_len == float('inf'):
            return 0
        else:
            return min_len