长度最小的连续子数组

[编程题]长度最小的连续子数组

热度指数：4167 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一个数组 nums 和一个正整数 target , 找出满足和大于等于 target 的长度最短的连续子数组并返回其长度，如果不存在这种子数组则返回 0。

数据范围：数组长度满足 $1 \le n \le 10^5 \$ ，数组中的元素满足 $1 \le val \le 10^5 \$ ， $1 \le target \le 10^5 \$

示例1

输入

[1,2,4,4,1,1,1],9

输出

示例2

输入

[1,4,4,4,1,1,1],3

输出

算法知识视频讲解

在写面经的咸鱼很机智

// C语言竟然没人提交,那我来个代码,仿生态模式滑窗思维

int minSubarray(int* nums, int numsLen, int target ) {

// write code here
    int resultA = 0, resultE= 0;
    int resultLength = 0,resultLengthMin = 1000000;
    int i,j,k,sum = 0;

    for(i = 0; i < numsLen; ++i) {
        sum += nums[i];
        if(sum >= target) {
            resultE = i;

            resultLength = resultE - resultA + 1;
            if(resultLengthMin > resultLength) {
                resultLengthMin = resultLength;
            }

            for(j = resultA; j < i; ++j) {
                sum -= nums[j];
                if(sum >= target) {
                    resultA = j + 1;
                    resultLength = resultE - resultA + 1;
                    if(resultLengthMin > resultLength) {
                        resultLengthMin = resultLength;
                    }
                }
                else {
                    // 不能减,切记复原
                    sum += nums[j];
                    break;
                }
            }

        }
    }

    return (resultLengthMin>=100000?0:resultLengthMin);
}

发表于 2023-05-17 02:58:41 回复(0)