526互联

长度最小的子数组

发布时间 2024-01-07 21:21:56作者: lulixiu

长度最小的子数组

暴力解法

int minSubArrayLen(int target, int* nums, int numsSize){
//初始化最小长度为INT_MAX
int minLength = INT_MAX;
int sum;

int left, right;
for(left = 0; left < numsSize; ++left) {
//每次遍历都清零sum，计算当前位置后和>=target的子数组的长度
sum = 0;
//从left开始，sum中添加元素
for(right = left; right < numsSize; ++right) {
sum += nums[right];
//若加入当前元素后，和大于target，则更新minLength
if(sum >= target) {
int subLength = right - left + 1;
minLength = minLength < subLength ? minLength : subLength;
}
}
}
//若minLength不为INT_MAX，则返回minLnegth
return minLength == INT_MAX ? 0 : minLength;
}

时间复杂度是n^2.

数组操作：滑动窗口

滑动窗口的精妙之处在于根据当前子序列和大小的情况，不断调节子序列的起始位置。从而将O(n^2)暴力解法降为O(n)。

一些录友会疑惑为什么时间复杂度是O(n)。

不要以为for里放一个while就以为是O(n^2)啊， 主要是看每一个元素被操作的次数，每个元素在滑动窗后进来操作一次，出去操作一次，每个元素都是被操作两次，所以时间复杂度是 2 × n 也就是O(n)。

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

int minSubArrayLen(int target, int* nums, int numsSize) {
//初始化最小长度为INT_MAX，计算机的极大值
int minLength = INT_MAX;
int sum = 0;

int left = 0, right = 0;//在滑动窗口算法中，我们需要在多次循环中保持 right 的状态。
//将 right = 0 放在循环内的话，每次循环开始时都会将 right 初始化为 0，
// 这样可能会导致在循环执行的过程中重新定义了 right 的初始值，而无法正确追踪窗口的位置。

for (; right < numsSize; ++right) {//右边界向右扩展
sum += nums[right];
//当sum的值大于等于target时，保存长度，并且收缩左边界
while (sum >= target) {
int subLength = right - left + 1;//// 取子序列的长度
minLength = minLength < subLength ? minLength : subLength;

sum -= nums[left++];// 这里体现出滑动窗口的精髓之处，不断变更left（子序列的起始位置）
//作用是减去当前子序列的左边界 left 所对应的元素，并将左边界向右移动一个位置。
// 这一操作是为了缩小当前的子序列范围，以便在下一次迭代中判断新的子序列是否满足条件。
}
}
//若minLength不为INT_MAX，则返回minLnegth
return minLength == INT_MAX ? 0 : minLength;
}
int main() {
int nums[] = { 2, 3, 1, 2, 4, 3 };
int s = 7;
int numsSize = sizeof(nums) / sizeof(nums[0]);

int result = minSubArrayLen(s, nums, numsSize);
printf("The minimum length of subarray whose sum is greater than or equal to %d is %d.\n", s, result);

return 0;
}

前缀+二分查找

为了使用二分查找，需要额外创建一个数组 sums 用于存储数组 nums 的前缀和，其中 sums[i] 表示从 nums[0] 到 nums[i−1] 的元素和。得到前缀和之后，对于每个开始下标 i，可通过二分查找得到大于或等于 i 的最小下标 bound，使得 sums[bound]−sums[i−1]≥s，并更新子数组的最小长度（此时子数组的长度是 bound−(i−1)）。

因为这道题保证了数组中每个元素都为正，所以前缀和一定是递增的，这一点保证了二分的正确性。如果题目没有说明数组中每个元素都为正，这里就不能使用二分来查找这个位置了。

int lower_bound(int* a, int l, int r, int q) {
// 如果数组的最后一个元素比目标值小，那么不存在符合要求的元素
if (a[r] < q)
return -1;

// 二分查找
while (l < r) {//左闭右开写法
int mid = (l + r) >> 1; // 计算中间位置
if (a[mid] >= q) { // 如果中间的数大于等于目标值，那么向左查找
r = mid;
}
else { // 否则向右查找
l = mid + 1;
}
}
return l; // 返回下界位置
}

int minSubArrayLen(int s, int* nums, int numsSize) {
// 若数组为空，直接返回0
if (numsSize == 0) {
return 0;
}

int ans = INT_MAX; // 结果初始化为整型最大值
int* sums = (int*)malloc(sizeof(int) * (numsSize + 1)); // 分配储存前缀和的数组空间
// 计算前缀和
for (int i = 1; i <= numsSize; i++) {
sums[i] = sums[i - 1] + nums[i - 1];
}
// 遍历数组中每个元素
for (int i = 1; i <= numsSize; i++) {
int target = s + sums[i - 1]; // 目标值为 s + 前缀和
int bound = lower_bound(sums, 1, numsSize, target); // 查找下界
if (bound != -1) { // 如果下界存在
ans = fmin(ans, bound - (i - 1)); // 更新最小长度
}
}
free(sums); // 释放前缀和数组的内存
return ans == INT_MAX ? 0 : ans; // 返回结果
}

时间复杂度：O(nlog⁡n)，其中 n 是数组的长度。需要遍历每个下标作为子数组的开始下标，遍历的时间复杂度是 O(n)，对于每个开始下标，需要通过二分查找得到长度最小的子数组，二分查找得时间复杂度是 O(logn)，因此总时间复杂度是 O(nlogn)。

int mid = (l + r) >> 1 什么意思

这行代码是一个常见的用来计算中间位置的技巧。在这行代码中，(l + r) 是左右边界的和，>> 1 是位运算中的右移操作符，用来将这个和除以2（向下取整），得到的结果就是中间位置的索引值。

实际上，使用位运算来执行除以2的操作比直接使用除法效率更高。在大多数计算机架构中，位运算的速度比算术运算更快，因此这种位运算的方式可以提高代码的执行效率。

总之，这行代码的作用是计算左右边界的中间位置，用于二分查找等算法中。