二分查找|滑动窗口|前缀和|LeetCode209: 长度最小的子数组

长度最短的子数组

作者推荐

【动态规划】【广度优先】LeetCode2258:逃离火灾

本文涉及的基础知识点

二分查找算法合集
C++算法：前缀和、前缀乘积、前缀异或的原理、源码及测试用例包括课程视频
滑动窗口

题目

给定一个含有 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 <= 10⁹
1 <= nums.length <= 10⁵
1 <= nums[i] <= 10⁵

枚举开始，二分结尾

时间复杂度：O(nlogn)。
vPreSum是前缀和，已知i，求子数组[i,j)的和大于等于target的最小j。
子数组[i,j)的和等于vPreSum[j]-vPreSum[i] ,大于等于target，则vPreSum[j] >= target + vPreSum[i]，我们选择第一个大于等于target + vPreSum[i]的数。

核心代码

class Solution {
public:
	int minSubArrayLen(int target, vector<int>& nums) {
		vector<long long> vPreSum = { 0 };
		for (const auto& n : nums)
		{
			vPreSum.emplace_back(n + vPreSum.back());
		}
		int iRet = INT_MAX;
		for (int i = 0; i < nums.size(); i++)
		{
			int j = std::lower_bound(vPreSum.begin(), vPreSum.end(), target + vPreSum[i]) - vPreSum.begin();
			if (vPreSum.size() == j)
			{
				continue;
			}
			iRet = min(iRet,j-i );
		}
		return (INT_MAX== iRet)? 0 : iRet;
	}
};

测试用例

template<class T>
void Assert(const vector<T>& v1, const vector<T>& v2)
{
	if (v1.size() != v2.size())
	{
		assert(false);
		return;
	}
	for (int i = 0; i < v1.size(); i++)
	{
		assert(v1[i] == v2[i]);
	}
}

template<class T>
void Assert(const T& t1, const T& t2)
{
	assert(t1 == t2);
}

int main()
{
	int target;
	vector<int> nums;
	{
		Solution slu;
		target = 7, nums = { 2, 3, 1, 2, 4, 3 };
		auto res = slu.minSubArrayLen(target, nums);
		Assert(2, res);
	}
	{
		Solution slu;
		target = 4, nums = { 1,4,4 };
		auto res = slu.minSubArrayLen(target, nums);
		Assert(1, res);
	}
	{
		Solution slu;
		target = 11, nums = { 1,1,1,1,1,1,1,1 };
		auto res = slu.minSubArrayLen(target, nums);
		Assert(0, res);
	}
	//CConsole::Out(res);
}

二分长度，利用滑动窗口求和

时间复杂度：O(nlogn)。
首先处理特殊情况：不存在合乎要求的子数组。
寻找第一个符合的长度，用左开右闭的二分。

class Solution {
public:
	int minSubArrayLen(int target, vector<int>& nums) {
		if (std::accumulate(nums.begin(), nums.end(), 0LL) < target)
		{
			return 0;
		}
		//左开右闭空间
		int left = 0, right = nums.size();
		while (right - left > 1)
		{
			const int mid = left + (right - left) / 2; 
			auto Is = [&]()
			{				
				long long llSum = 0;
				int i = 0;
				for (; i < mid; i++)
				{
					llSum += nums[i];
				}
				if (llSum >= target)
				{
					return true;
				}
				for (; i < nums.size(); i++)
				{
					llSum += nums[i] - nums[i - mid];
					if (llSum >= target)
					{
						return true;
					}
				}
				return false;
			};
			if (Is())
			{
				right = mid;
			}
			else
			{
				left = mid;
			}
		}
		return right;
	}
};

滑动窗口

两层枚举，第一层从大到小枚举left，第二层枚举right。两层时间复杂度都是O(n)，第二层枚举没有从新开始，所以总时间复杂度是O(n)。子数组[left,right)是以下情况之一：
一，[left,right)是第一个小于target的right。
二，right是m_c。对应没有符合要求的以left开始的子数组。

class Solution {
public:
	int minSubArrayLen(int target, vector<int>& nums) {
		m_c = nums.size();
		long long llSum =0;
		int iRet = INT_MAX;
		for (int left = m_c - 1, right = m_c; left >= 0; left--)
		{
			llSum += nums[left];
			while (llSum >= target)
			{
				right--;
				llSum -= nums[right];
			}
			if (m_c != right)
			{
				iRet = min(iRet, right - left + 1);
			}
		}
		return (INT_MAX==iRet)?0:iRet;
	}
	int m_c;
};