leetcode 209m 长度最小的子数组

Published on:
Tags: leetcode

题目描述#

给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的连续子数组，并返回其长度。如果不存在符合条件的连续子数组，返回 0。

 
示例：

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

数组元素 和 s均为正整数，即均大于0

算法#

  1. 定义两个数组下标：i j，遍历数组
  2. 外层循环i表示子数组的起点下标，内层循环j从位置i开始，逐个累加数组元素,同时计算数组元素个数tmplength，直到累加和大于等于s 或者 j大于等于元素个数numsSize 时停止
  3. 取得最小的元素个数

当 $i=0,j=numsSize-1,sum<s$ 时，即是：整个数组的和小于s，直接返回0

类似的，
当 $i>0,j=numsSize-1,sum<s$ 时，即是：从i到j的累加和小于s，表示i后面的元素累加和都小于s，不存在符合条件的子数组，直接跳出循环

C代码#

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
#include <stdio.h>

int minSubArrayLen(int s, int* nums, int numsSize);

int main()
{
    int s = 3,numsSize = 2;
    int nums[2] = {1,1};
    int length = minSubArrayLen( s, &nums[0],  numsSize);
    printf("长度最小的子数组长度length=%d",length);
    return 0;
}

int minSubArrayLen(int s, int* nums, int numsSize)
{
    int length = numsSize;  

    for(int i=0;i<numsSize;i++)
    {    
        int sum = 0,tmpLength = 0,j;
        
        for(j=i;j<numsSize && sum<s;j++)
        {
            sum += nums[j];
            tmpLength++;
        }
        
        if(sum < s)
        {
            if(i == 0) return 0;   
            else break; 
        }

        if(tmpLength < length) length = tmpLength;
        printf("i=%d,j=%d,tmpLength=%d,sum=%d\n",i,j,tmpLength,sum);
    }

    return length;
}

时间复杂度#

算法的时间复杂度为 $O(n)$