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

## 题目

1 <= target <= 109

1 <= nums.length <= 105

1 <= nums[i] <= 105

## 枚举开始，二分结尾

vPreSum是前缀和，已知i，求子数组[i,j)的和大于等于target的最小j。

### 核心代码

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);
}

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

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;
}
};

## 滑动窗口

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;
};

## 扩展阅读

#### 视频课程

https://edu.csdn.net/course/detail/38771

https://edu.csdn.net/lecturer/6176

#### 相关下载

。也就是我们常说的专业的人做专业的事。 |

|如果程序是一条龙，那算法就是他的是睛|

#### 测试环境

VS2022 C++17

|
30天前
|

LeetCode刷题---209. 长度最小的子数组（双指针-滑动窗口）
LeetCode刷题---209. 长度最小的子数组（双指针-滑动窗口）
27 0
|
3天前
|

6 1
|
24天前
|

34 4
|
30天前
|

leetcode代码记录（最长重复子数组
leetcode代码记录（最长重复子数组
15 0
|
30天前
leetcode代码记录（长度最小的子数组
leetcode代码记录（长度最小的子数组
18 0
|
30天前
【力扣】209. 长度最小的子数组
【力扣】209. 长度最小的子数组
30 0
|
30天前
|

19 1
|
18天前
|

【力扣刷题】两数求和、移动零、相交链表、反转链表
【力扣刷题】两数求和、移动零、相交链表、反转链表
22 2
|
1天前
|

【LeetCode刷题】只出现一次的数字（Ⅰ、Ⅱ、Ⅲ）
【LeetCode刷题】只出现一次的数字（Ⅰ、Ⅱ、Ⅲ）
6 0
|
7天前
|

9 0