image-20241101084622114

暴力

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int minSubArrayLen(int target, int* nums, int numsSize) {
    int min=10000;
    for(int i=0;i<numsSize;i++){
        if(nums[i]>=target){
            return 1;
            break;
        }
        int sum=nums[i];
        for(int j=i+1;j<numsSize;j++){
            sum+=nums[j];
            if(sum>=target&&(j-i+1)<min){
                min=j-i+1;
                break;
            }
        }
    }
    if(min!=10000){
        return min;
    }else{
        return 0;
    }
}

image-20241101090340884

一个超大的测试用例,直接超时了

题解

  • 使用滑动窗口知识

    1
    2
    3
    4
    5
    6
    1. 使用左右指针left和right,left和right之间的长度即为滑动窗口的大小
    2. 如果滑动窗口内的值sum>=target,维护连续数组最短长度,left向右移动,缩小滑动窗口
    3. 如果滑动窗口内的值sum<target,则right向右移动,扩大滑动窗口

    本题解 left 指针和 right 指针最多只遍历数组 1 次，所以时间复杂度为 O(n)。
    只额外开了 2 个指针，空间复杂度为 O(1)。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

int min(int a, int b) {
    return (a < b) ? a : b;
}
int minSubArrayLen(int target, int* nums, int numsSize) {
    int left=0;
    int sum=0;
    int result=INT_MAX;
    for(int right=0;right<numsSize;right++){
        sum+=nums[right];
        while(sum>=target){
            result=min(result,right-left+1);
            sum-=nums[left++];
        }
    }
    return result==INT_MAX?0:result;
}

image-20241101092039803

java代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public int min(int a,int b){
        return a>b?b:a;
    }

    public int minSubArrayLen(int target, int[] nums) {
        int left=0,sum=0;
        int result=Integer.MAX_VALUE;
        for (int right = 0; right < nums.length; right++) {
            sum+=nums[right];
            while(sum>=target){
                result=min(result,right-left+1);
                sum-=nums[left++];
            }
        }
        return result==Integer.MAX_VALUE?0:result;
    }

参考博客:ACM 选手玩转 LeetCode 滑动窗口解决长度最小的子数组