209. 长度最小的子数组

作者 : admin 本文共1566个字,预计阅读时间需要4分钟 发布时间: 2024-06-16 共1人阅读

链接

暴力法

未能通过全部测试用例。

C 代码:

// 计算子数组的和
int getSum(int start, int end, int* nums) {
    int sum = 0;
    while (start <= end) {
        sum += nums[start];
        start++;
    }
    return sum;
}

int minSubArrayLen(int target, int* nums, int numsSize) {
    int min = numsSize + 1; // 初始化最小子数组长度为数组长度加 1
    bool flag = false; // 定义一个布尔值表示是否找到了满足条件的子数组
    int i, j;
    for (i = 0; i < numsSize; i++) {                   // 遍历数组
        for (j = i, flag = false; j < numsSize; j++) { // 从当前元素开始往后找
            if (getSum(i, j, nums) >= target) {
                flag = true;
                break;
            }
        }
        // 如果确实找到了,那么判断是否需要更新最短值
        if (flag == true && j - i + 1 < min) {
            min = j - i + 1;
        }
    }
    if (min == numsSize + 1) {
        return 0;
    } else {
        return min;
    }
}

结果:超出时间限制, 18 / 21 个通过的测试用例

官方解答:

int minSubArrayLen(int s, int* nums, int numsSize) {
    if (numsSize == 0) {
        return 0;
    }
    int ans = INT_MAX;
    for (int i = 0; i < numsSize; i++) {
        int sum = 0;
        for (int j = i; j < numsSize; j++) {
            sum += nums[j];
            if (sum >= s) {
                ans = fmin(ans, j - i + 1);
                break;
            }
        }
    }
    return ans == INT_MAX ? 0 : ans;
}

结果相同。包括通过测试用例的个数,也完全相同。

复杂度分析

时间复杂度:

O

(

n

2

)

O(n^2)

O(n2),其中 n 是数组的长度。需要遍历每个下标作为子数组的开始下标,对于每个开始下标,需要遍历其后面的下标得到长度最小的子数组。

空间复杂度:

O

(

1

)

O(1)

O(1)

滑动窗口法

一个未能通过全部测试用例的 C 代码:

int getSum(int start, int end, int* nums) {
    int sum = 0;
    for (; start <= end; start++) {
        sum += nums[start];
    }
    return sum;
}

int minSubArrayLen(int target, int* nums, int numsSize) {
    int start = 0, end = 0;
    int min = numsSize + 1;
    int sum = 0;
    for (; end < numsSize; end++) {
        sum = getSum(start, end, nums);
        while (sum >= target) {
            min = end - start + 1;
            sum -= nums[start];
            start++;
        }
    }
    if (min == numsSize + 1) {
        return 0;
    } else {
        return min;
    }
}
解答错误  15 / 21 个通过的测试用例

输入:

target  = 15
nums = [5,1,3,5,10,7,4,9,2,8]

输出:

3

预期结果:

2

通过全部测试用例的 C 代码:

int minSubArrayLen(int target, int* nums, int numsSize) {
    int start = 0, end = 0;
    int min = numsSize + 1;
    int sum = 0;
    for (; end < numsSize; end++) {
        sum += nums[end];
        while (sum >= target) {
            min = fmin(min, end - start + 1);
            sum -= nums[start];
            start++;
        }
    }
    return min == numsSize + 1 ? 0 : min;
}
本站无任何商业行为
个人在线分享-虚灵IT资料分享 » 209. 长度最小的子数组
E-->