60、【数组】leetcode——209. 长度最小的子数组-滑动窗口:最小窗口(C++、Python版本)
题目描述
原题链接:
209. 长度最小的子数组
题中条件
(1)正整数;(2)目标子序列为连续的;(3)目标为连续的子序列中长度最小的;
根据这两个特性,主要需要解决两个问题:
(1)找出满足条件的连续子序列
(2)找出各个子序列中长度最小的那个子序列
由此可以将问题转化为上述两个子问题,首先第一步找出满足条件的连续子序列,也就是遍历数组求和,找出满足≥target
的序列。
找到后,记录该子序列的长度。与其已有长度进行比较,若更小则更新,若没有比其更小,则不记录该序列。
以此方式,对下一个子序列进行遍历求和、比较长度,最终找到最小子序列。
1. 暴力破解
用两个for循环找到每个子序列,第一个for循环中的控制变量为子序列的“头”,第二个for循环的控制变量为子序列的“尾”。
求和比较在第二个for循环中进行。
C++版本
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
int length = INT32_MAX; // 初始时设为极大值
int sum;
for(int i = 0; i < nums.size(); i++){ //
sum = 0;
for(int j = i; j < nums.size(); j++){
sum += nums[j];
if(sum >= target){ // 若满足条件,则将此序列长度与已有长度进行比较
length = j - i + 1 < length ? j - i + 1 : length; // 因为下标从0开始,所以要加1
break;
}
}
}
return length == INT32_MAX ? 0 : length;
}
};
Python版本
class Solution:
def minSubArrayLen(self, target: int, nums: List[int]) -> int:
length = 2*len(nums)
for i in range(len(nums)):
sum = 0
for j in range(i, len(nums)):
sum += nums[j]
if sum >= target:
length = min(length, j - i + 1)
break
return 0 if length == 2*len(nums) else length
空间复杂度
O
(
1
)
O(1)
O(1)
时间复杂度
O
(
n
2
)
O(n^2)
O(n2)
2. 双指针法:滑动窗框
本题目标是求出最小的窗口长度。
用快慢指针实现滑动窗口,使用滑动窗口模型找出符合条件的子序列。
当找到满足条件子序列时,对比此序列长度是否小于已有长度。若小于,则记录。否则,不记录。然后,将滑动窗口的左端向右进行收缩,收缩至正好不满足条件子序列是,再进行向右扩展。
C++版本
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
int n = nums.size();
int sum = 0, res = INT32_MAX;
for(int i = 0, j = 0; j < n; j++){ // i为尾端快指针,j为头端慢指针
sum += nums[j]; // 尾指针向右扩展窗口
// 注意这里要先用while收缩再比较,找到最短的长度再进行记录。例子:4 [1,4,4]。
// 如果只用if的话,外层的j会提前跳出循环,导致得到的不为最小长度
while(sum >= target){
res = min(res, j - i + 1);
sum -= nums[i++];
}
//j++; // 注意到一轮结束后再j++,提前j++会影响j - i + 1的结果
}
return res == INT32_MAX ? 0 : res;
}
};
Python版本
class Solution:
def minSubArrayLen(self, target: int, nums: List[int]) -> int:
left, sum, res = 0, 0, 2*len(nums)
for right in range(len(nums)) :
sum += nums[right]
while sum - nums[left] >= target :
sum -= nums[left]
left += 1
if sum >= target :
res = min(res, right - left + 1)
return 0 if sum < target else res
空间复杂度
O
(
1
)
O(1)
O(1)
时间复杂度
O
(
n
)
O(n)
O(n)
拓展资料
相关文章
- Python虚拟环境的安装和配置-virtualenv与windows下多个python版本共存
- 【Python成长之路】从 零做网站开发 -- 基于Flask和JQuery,实现表格管理平台
- 【Python成长之路】Python爬虫 --requests库爬取网站乱码(xe4xb8xb0xe5xa)的解决方法【华为云分享】
- python简单的函数定义和用法实例
- python-django-redis拒绝连接问题解决_20191121
- Python 爬虫开发:Ajax请求响应json案例
- Atitit web httphandler的实现 java python node.js c# net php 目录 1.1. Java 过滤器 servelet1 1.2. Python的
- Python 异步网络爬虫教程大全
- Python语言学习之文件夹那些事:python和文件夹的使用方法之详细攻略
- Python:更改默认启动的python程序及其对应的安装包路径(更改pip的默认安装包的路径)图文教程之详细攻略
- Python之API:基于python语言调用华为云API(华为网站)实现特定功能
- 已解决2.Set PROTOCOL_BUFFERS_PYTHON_IMPLEMENTATION=python (but this will use pure-Python parsing and wi
- 〖Python接口自动化测试实战篇⑧〗- 小案例 - 使用python实现接口请求 [查询天行数据]
- 从C、C++、Java到Python,编程入门到底学什么语言好?
- 【华为OD机试 2023】 去除多余空格(C++ Java JavaScript Python)
- 【 华为OD机试 2023】 最大平分数组(C++ Java JavaScript Python)
- 【华为OD机试 2023】最优高铁城市修建方案(C++ Java JavaScript Python)
- C++学习心得与c语言到c++衔接技巧
- Python编程:python面向对象
- python 设计模式之装饰器模式 Decorator Pattern
- Python Word2Vec使用训练好的模型生成词向量
- yolov4视频目标检测:使用C++版本联合CUDA11.2的OpenCV 5.x编译生成opencv-python==5.x进行推理
- 让 Python 代码更易维护的七种武器——代码风格(pylint、Flake8、Isort、Autopep8、Yapf、Black)测试覆盖率(Coverage)CI(JK)
- python基础===一行 Python 代码实现并行(转)
- python 爬虫 循环分页
- 使用python实现对样本的分层均衡抽样
- 第十三届蓝桥杯Java、C++、Python组国赛真题——最大公约数(三语言AC)
- 【异常】前端ERR! stack Error: Can‘t find Python executable “python“, you can set the PYTHON env variable.
- python库Django链接mysql数据库做网站(一)--构建基本结构访问静态页面