209.长度最小的子数组

题目描述

给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的子数组。如果不存在符合条件的子数组，返回 0。

解题思路

使用滑动窗口的思想解决该问题。定义两个指针，分别表示滑动窗口的左右边界，通过移动右边界来扩展窗口，移动左边界来缩小窗口。在移动的过程中，实时更新滑动窗口内的元素和，并记录最小子数组的长度。

解题步骤

1. 初始化左指针 left 和右指针 right，它们初始都指向数组的第一个元素。
2. 初始化变量 minLen 表示最小子数组的长度，设置为正无穷大。
3. 初始化变量 sum 表示当前滑动窗口内元素的和，初始值为0。
4. 使用循环移动右指针 right，直到滑动窗口内元素和大于等于目标值 s
   如果 sum 大于等于目标值 s，更新 minLen 为当前窗口长度，并向左移动左指针 left 缩小窗口，更新 sum。
5. 重复步骤4，直到右指针到达数组末尾。
6. 如果 minLen 仍然是初始值，说明不存在满足条件的子数组，返回0；否则，返回 minLen。

特殊案例

• 如果输入数组为空，则直接返回0。

C#代码实现

public int MinSubArrayLen(int s, int[] nums) {
   
    if (nums == null || nums.Length == 0) {
   
        return 0;
    }

    int left = 0;
    int right = 0;
    int minLen = int.MaxValue;
    int sum = 0;

    while (right < nums.Length) {
   
        sum += nums[right];

        while (sum >= s) {
   
            minLen = Math.Min(minLen, right - left + 1);
            sum -= nums[left];
            left++;
        }

        right++;
    }

    return minLen == int.MaxValue ? 0 : minLen;
}

C代码实现

int minSubArrayLen(int s, int* nums, int numsSize) {
   
    if (nums == NULL || numsSize == 0) {
   
        return 0;
    }

    int left = 0;
    int right = 0;
    int minLen = INT_MAX;
    int sum = 0;

    while (right < numsSize) {
   
        sum += nums[right];

        while (sum >= s) {
   
            minLen = fmin(minLen, right - left + 1);
            sum -= nums[left];
            left++;
        }

        right++;
    }

    return minLen == INT_MAX ? 0 : minLen;
}

时间复杂度和空间复杂度

• 时间复杂度：O(n)，其中 n 是数组 nums 的长度。每个元素至多被访问两次，即左指针和右指针各一次。
• 空间复杂度：O(1)。除了常数级别的变量，算法的空间复杂度是常数级别的。