当前位置：首页 > news >正文

【代码随想录】长度最小的子数组——滑动窗口

news 来源：原创 2024/9/19 7:28:20

本博文为《代码随想录》的学习笔记。原文链接：代码随想录

题目

原题链接：长度最小的子数组

给定一个含有 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)) 时间复杂度的解法。

题解

为了适应机试环境，首先在Dev C++中编写程序。对输入输出示例略加改动。

输入：target，数组长度n，nums数组元素

输出：子数组长度

示例一：

输入：7 6 2 3 1 2 4 3

输出：2

示例二：

输入：4 3 1 4 4

输出：1

示例三：

输入：11 8 1 1 1 1 1 1 1 1

输出：0

方法一：暴力解法

在Dev C++中编写程序

#include <bits/stdc++.h>
using namespace std;int minSubArrayLen(int target, vector<int>& nums)
{int ans=0,length=nums.size();//ans为当前相加个数，length为最小相加个数 int result=0,flag=0;//result为当前子数组元素和，flag标记是否存在总和大于等于target的子数组 for(int i=0;i<nums.size();i++){ans=0;for(int j=i;j<nums.size();j++) {result+=nums[j];ans++;if(result>=target){flag=1;if(length>=ans){length=ans;    }break;}}result=0;}if(flag==0)return 0;else return length;}
int main()
{int target,n;	cin>>target>>n;vector<int>nums;for(int i=0;i<n;i++){int ans;cin>>ans;nums.push_back(ans);}int length = minSubArrayLen(target,nums); // 调用你的实现cout<<length;return 0;
}

在LeetCode中运行

class Solution {
public:int minSubArrayLen(int target, vector<int>& nums) {int ans = 0,length = nums.size(); // ans为当前相加个数，length为最小相加个数int result = 0,flag =0; // result为当前子数组元素和，flag标记是否存在总和大于等于target的子数组for (int i = 0; i < nums.size(); i++) {ans = 0;for (int j = i; j < nums.size(); j++) {result += nums[j];ans++;if (result >= target) {flag = 1;if (length >= ans) {length = ans;}break;}}result = 0;}if (flag == 0)return 0;elsereturn length;}
};

对比《代码随想录》中给出的代码，发现可以使用以下语句代替if条件判断缩短代码长度

result = result < subLength ? result : subLength;

// 如果result没有被赋值的话，就返回0，说明没有符合条件的子序列
return result == INT32_MAX ? 0 : result;

时间复杂度：O(n^2)
空间复杂度：O(1)

暴力算法超时。

方法二：滑动窗口

所谓滑动窗口，就是不断地调节子序列地起始位置和终止位置，从而得出我们想要的结果。

在暴力解法中，是一个for循环滑动窗口的起始位置，一个for循环为滑动窗口的终止位置，用两个for循环完成了一个不断搜索区间的过程。

那么滑动窗口如何用一个for循环来完成这个操作呢。

首先要思考，如果用一个for循环，那么应该表示滑动窗口的起始位置还是终止位置。

如果只用一个for循环来表示滑动窗口的起始位置，那么如何遍历剩下的终止位置？此时难免再次陷入暴力解法的怪圈。所以，只使用一个for循环，那么这个循环的索引一定表示滑动窗口的终止位置。

以题目中的示例举例，s=7，数组是2，3，1，2，4，3，观察滑动窗口的起始位置如何移动。

在本题中实现滑动窗口，主要确定以下三点：

窗口内是什么？
如何移动窗口的起始位置？
如何移动窗口的终止位置？

窗口就是满足其和>=s的长度最小的连续子数组。

窗口的起始位置如何移动：如果当前窗口的值大于等于s了，窗口起始位置就要向前移动了（也就是该缩小了）。

窗口的结束位置如何移动：窗口的结束位置就是遍历数组的指针，也就是for循环里的索引。

解题的关键在于窗口的起始位置如何移动，如图所示：

可以发现滑动窗口的精妙之处在于根据当前子序列和大小的情况，不断调节子序列的起始位置。从而将O(n^2)暴力解法降为O(n)。

先在Dev C++中编写程序

#include <bits/stdc++.h>
using namespace std;int minSubArrayLen(int target, vector<int>& nums)
{int ans=0,length=nums.size();//ans为滑动窗口长度，length为最小相加个数 int result=0,flag=0;//result为当前子数组元素和，flag标记是否存在总和大于等于target的子数组 int i=0;//滑动窗口的起始位置 for(int j=0;j<nums.size();j++){result+=nums[j];ans++; while(result>=target){flag=1;length=length<ans?length:ans;result-=nums[i];i++;ans--;	}}if(flag==0)return 0;else return length;}
int main()
{int target,n;	cin>>target>>n;vector<int>nums;for(int i=0;i<n;i++){int ans;cin>>ans;nums.push_back(ans);}int length = minSubArrayLen(target,nums); // 调用你的实现cout<<length;return 0;
}

在LeetCode中运行

时间复杂度：O(n)
空间复杂度：O(1)

不要以为for里放一个while就以为是O(n^2)啊，主要是看每一个元素被操作的次数，每个元素在滑动窗后进来操作一次，出去操作一次，每个元素都是被操作两次，所以时间复杂度是 2 × n 也就是O(n)。

与《代码随想录》中给出的代码进行对比，注意标** 的代码简洁之处。

class Solution {
public:int minSubArrayLen(int target, vector<int>& nums) {int result = INT32_MAX;//** 因为要求最小子序列，将result初始值设为极大，在return时可以轻易判断出是否有符合要求的子序列int sum = 0;       // 滑动窗口数值之和int i = 0;         // 滑动窗口起始位置int subLength = 0; // 滑动窗口长度for (int j = 0; j < nums.size(); j++) {sum += nums[j];// 注意这里使用while,每次更新i（起始位置），并不断比较滑动窗口序列是否符合条件while (sum >= target) {subLength = (j - i + 1); // ** 取滑动窗口的长度result = result < subLength ? result : subLength;sum -= nums[i++]; // 这里体现出滑动窗口的精髓之处，不断变更i（子序列的起始位置）
//** 相当于sum-=nums[i];i++;}}return result == INT32_MAX ? 0 : result;}
};