【力扣】209. 长度最小的子数组

简介: 【力扣】209. 长度最小的子数组

209. 长度最小的子数组

题目描述

给定一个含有 n 个正整数的数组和一个正整数 target

找出该数组中满足其总和大于等于 target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ,并返回其长度。如果不存在符合条件的子数组,返回 0

示例 1:

输入:target = 7, nums = [2,3,1,2,4,3]

输出:2

解释:子数组 [4,3] 是该条件下的长度最小的子数组。

示例 2:

输入:target = 4, nums = [1,4,4]

输出:1

示例 3:

输入:target = 11, nums = [1,1,1,1,1,1,1,1]

输出:0

提示:

  • 1 <= target <= 109
  • 1 <= nums.length <= 105
  • 1 <= nums[i] <= 105

进阶:

  • 如果你已经实现 O(n) 时间复杂度的解法, 请尝试设计一个 O(n log(n)) 时间复杂度的解法。

解题方法

  • C 暴力双循环——超时
int mymin(int a, int b) {
    if (a > b)
        return b;
    else
        return a;
}

int minSubArrayLen(int target, int* nums, int numsSize) {
    int count = INT_MAX;
    if (numsSize == 0) {
        return 0;
    }
    for (int i = 0; i < numsSize; i++) {
        int sum = 0;
        for (int j = i; j < numsSize; j++) {
            sum = sum + nums[j];
            if (sum >= target) {
                count = mymin(count, j - i + 1);
                break;
            }
        }
    }

    return count == INT_MAX ? 0 : count;
}
  • C 滑动窗口法
int mymin(int a, int b) {
    if (a > b)
        return b;
    else
        return a;
}

int minSubArrayLen(int target, int* nums, int numsSize) {
    int count = INT_MAX;
    int start = 0, end = 0; // 定义窗口开始、结束
    int sum = 0;
    if (numsSize == 0) {
        return 0;
    }
    while (end < numsSize) {
        sum = sum + nums[end]; // 求窗口中元素和
        while (sum >= target) {
            count = mymin(count, end - start + 1); // 求最小窗口
            sum = sum - nums[start];               // 求和
            start++;                               // 缩小窗口
        }
        end++; // 增大窗口
    }
    return count == INT_MAX ? 0 : count;
}


复杂度分析

时间复杂度为 O(n),其中 n 是数组的长度。

空间复杂度为 O(1)。







相关文章
|
19天前
|
算法 测试技术 程序员
力扣经典150题第三十题:长度最小的子数组
力扣经典150题第三十题:长度最小的子数组
9 1
|
7天前
|
存储 算法
经典的滑动窗口的题目 力扣 2799. 统计完全子数组的数目(面试题)
经典的滑动窗口的题目 力扣 2799. 统计完全子数组的数目(面试题)
|
1月前
|
存储
力扣-2904最短且字典序最小的美丽子序列
力扣-2904最短且字典序最小的美丽子序列
15 1
|
20天前
技术经验解读:【LeetCode】560.SubarraySumEqualsK子数组和为K
技术经验解读:【LeetCode】560.SubarraySumEqualsK子数组和为K
|
2月前
|
人工智能
力扣100114. 元素和最小的山形三元组 II(中等)
力扣100114. 元素和最小的山形三元组 II(中等)
|
1月前
【LeetCode刷题】滑动窗口思想解决问题:长度最小的子数组、无重复字符的最长子串
【LeetCode刷题】滑动窗口思想解决问题:长度最小的子数组、无重复字符的最长子串
|
2月前
|
索引
leetcode代码记录(最长重复子数组
leetcode代码记录(最长重复子数组
19 0
|
2月前
leetcode代码记录(长度最小的子数组
leetcode代码记录(长度最小的子数组
21 0
|
1月前
|
算法 C++
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题-2
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题
|
1月前
|
算法 C++
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题-1
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题