209. 长度最小的子数组(Leetcode刷题笔记)
欢迎大家访问我的GitHub博客
https://lunan0320.cn
文章目录
题目
给定一个含有 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
解题代码 C++(核心)
解题思路： 使用的是滑动窗口（也可说是双指针，但是不太准确） 此类题目的关键是窗口前移的部分，有点动态的意思
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
int res = INT_MAX; //最小窗口
int sublength = 0; //滑动窗口长度
int sums = 0; //窗口内的数值之和
int begin = 0; //窗口起始点
int length = nums.size();
for(int end = 0; end < length; end++){
//依次遍历每一个值
sums += nums[end];
//起始位置的循环前移
while(sums >= target){
sublength = end - begin + 1;
res = res < sublength ? res : sublength;
sums -= nums[begin++];
}
}
return res == INT_MAX ? 0 : res;
}
};
解题代码 C++(本地编译运行)
//head.h
#pragma once
#include <iostream>
#include <vector>
#include <string>
using namespace std;
// Solution.h
//滑动窗口
class Solution4 {
public:
int minSubArrayLen(int target, vector<int>& nums) {
int res = INT_MAX;//最小窗口大小
int subLength = 0; //当前窗口大小
int begin = 0; //窗口起始
int sum = 0;
for (int end = 0; end < nums.size(); end++) {
//遍历
sum += nums[end];
while (sum >= target) {
subLength = end - begin + 1;
res = res < subLength ? res : subLength;
//窗口前移关键
sum -= nums[begin++];
}
}
return res;
}
};
//main.cpp
#include "Solution2.h"
int main() {
Solution4 solution;
vector<int> nums = { 2,3,1,2,4,3 };
int target = 7;
cout << solution.minSubArrayLen(target, nums) << endl;
}
算法效率
执行用时： 4 ms , 在所有 C++ 提交中击败了 94.40% 的用户
内存消耗：10.3 MB , 在所有 C++ 提交中击败了55.44% 的用户