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
)
O(n^2)
O(n2)，其中 n 是数组的长度。需要遍历每个下标作为子数组的开始下标，对于每个开始下标，需要遍历其后面的下标得到长度最小的子数组。
空间复杂度：
O
(
1
)
O(1)
O(1)。
