ARTS 打卡第 4 周

2023-09-10
浙江
本文字数：934 字
阅读完需：约 3 分钟

题图摄于 2020 年 1 月哈尔滨雪谷翻越雪山途中

1.Algorithm: 每周至少做一个 LeetCode 的算法题

题目：长度最小的子数组

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

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

'''示例'''输入：target = 7, nums = [2,3,1,2,4,3]输出：2解释：子数组 [4,3] 是该条件下的长度最小的子数组。
输入：target = 11, nums = [1,1,1,1,1,1,1,1]输出：0
'''提示'''1 <= target <= 10(9)1 <= nums.length <= 10(5)1 <= nums[i] <= 10(5)

复制代码

解法总结

核心就是滑动窗口

int minSubArrayLen(int target, vector<int>& nums) {        int left = 0, right = 0;        int min_num = INT_MAX;        int cur_sum = 0; // 滑动窗口数值之和        while (right < nums.size()) {            cur_sum += nums[right];            right++;            while (cur_sum >= target) {                int current_num = right - left;                min_num = min(min_num, current_num);                cur_sum -= nums[left];                left++;            }        }        if (min_num == INT_MAX) return 0;        else return min_num;    }