209. 长度最小的子数组

链接

暴力法

未能通过全部测试用例。

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)$，其中 n 是数组的长度。需要遍历每个下标作为子数组的开始下标，对于每个开始下标，需要遍历其后面的下标得到长度最小的子数组。

空间复杂度：$O(1)$。

前缀和 + 二分查找