算法学习Day 2|

209. 长度最小的子数组

用于寻找数组中和至少为s的最短连续子数组的长度

注意这个题是切割，不是随机选择，别想多了

法一：暴力解法，直接用两层for 循环

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
        #nums.sort()  #默认升序，原地修改，不额外占用
        #nums.sort(reverse=True)  # 降序排序
        #sorted_nums = sorted(nums, reverse=True)  # 降序生成新列表
        #sorted_nums = sorted(nums)  # 升序生成新列表
class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        l = len(nums)
        ans = l+1
        for i in range(l):
            a = 0
            for j in range(i,l):
                a += nums[j]
                if a >= target:
                    ans = min(ans,j - i + 1)
                    break
        return ans if ans <= l else 0

'''DS给个示例演示'''
假设输入为 s=7, nums=[2,3,1,2,4,3]，运行过程如下：

i=0（起始位置为0）：
j=0: cur_sum=2 → 不满足
j=1: cur_sum=2+3=5 → 不满足
j=2: cur_sum=5+1=6 → 不满足
j=3: cur_sum=6+2=8 ≥7 → 子数组长度=4 → min_len=4，跳出内层循环
i=1（起始位置为1）：
j=1: cur_sum=3 → 不满足
j=2: cur_sum=3+1=4 → 不满足
j=3: cur_sum=4+2 → 不满足
j=4: cur_sum=6+4=10 ≥7 → 子数组长度=4 → min_len仍为4，跳出内层循环
i=2（起始位置为2）：
j=2: cur_sum=1 → 不满足
j=3: cur_sum=1+2=3 → 不满足
j=4: cur_sum=3+4=7 ≥7 → 子数组长度=3 → min_len=3，跳出内层循环
i=3（起始位置为3）：
j=3: cur_sum=2 → 不满足
j=4: cur_sum=2+4=6 → 不满足
j=5: cur_sum=6+3=9 ≥7 → 子数组长度=3 → min_len仍为3，跳出内层循环
i=4（起始位置为4）：
j=4: cur_sum=4 → 不满足
j=5: cur_sum=4+3=7 ≥7 → 子数组长度=2 → min_len=2，跳出内层循环
i=5（起始位置为5）：
j=5: cur_sum=3 → 不满足
最终 min_len=2，即最短子数组为 [4,3]。

法二：滑动窗口法（重点）

时间复杂度O（n）（2n）

空间复杂度O（1）

应用场景：单调性

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        n = len(nums)
        ans = n + 1  # 也可以写 inf
        s = left = 0
        for right, x in enumerate(nums):  # 枚举子数组右端点
            s += x
            while s - nums[left] >= target:  # 尽量缩小子数组长度
                s -= nums[left]
                left += 1  # 左端点右移
            if s >= target:
                ans = min(ans, right-left+1)
        return ans if ans <= n else 0

59.螺旋矩阵II