209.长度最小的子数组
209.1 题目
给定一个含有 n 个正整数的数组和一个正整数 target。
找出该数组中满足其总和大于等于 target 的长度最小的子数组 [nums[l], nums[l+1], ..., nums[r-1], nums[r]]，并返回其长度。如果不存在符合条件的子数组，返回 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^91 <= nums.length <= 10^51 <= nums[i] <= 10^5
进阶：
如果你已经实现 O(n) 时间复杂度的解法，请尝试设计一个 O(n log(n)) 时间复杂度的解法。
209.2 题解
滑动窗口
// 方法一：滑动窗口
// 使用滑动窗口来找到满足条件的最小子数组长度
static int MinSubArrayLen1(int target, int[] nums)
{
// 初始化最小长度为正无穷
int minLength = int.MaxValue;
// 初始化滑动窗口的左指针和当前窗口的总和
int left = 0, sum = 0;
// 遍历数组中的每个元素，i为滑动窗口的右指针
for (int i = 0; i < nums.Length; i++)
{
// 将当前元素加入窗口的总和
sum += nums[i];
// 当窗口内的总和大于等于目标值时，尝试收缩窗口
while (sum >= target)
{
// 更新最小长度
minLength = Math.Min(minLength, i - left + 1);
// 从窗口总和中移除最左侧的元素
sum -= nums[left];
// 将左指针右移一位
left++;
}
}
// 如果minLength没有更新过，说明没有符合条件的子数组，返回0；否则返回最小长度
return minLength == int.MaxValue ? 0 : minLength;
}
前缀和 + 二分查找
// 方法二：前缀和 + 二分查找
// 使用前缀和数组和二分查找来找到满足条件的最小子数组长度
static int MinSubArrayLen2(int target, int[] nums)
{
// 获取数组的长度
int numsLength = nums.Length;
// 如果数组为空，返回0
if (numsLength == 0)
{
return 0;
}
// 初始化最小长度为正无穷
int minLength = int.MaxValue;
// 初始化前缀和数组，长度为numsLength + 1
int[] sums = new int[numsLength + 1];
// 计算前缀和数组
for (int i = 1; i <= numsLength; ++i)
{
// 当前前缀和等于前一个前缀和加上当前元素
sums[i] = sums[i - 1] + nums[i - 1];
}
// 遍历前缀和数组
for (int i = 1; i <= numsLength; ++i)
{
// 计算目标前缀和
// 假设我们要找的子数组为 nums[l] 到 nums[r]，那么这个子数组的和为 sums[r + 1] - sums[l]。
// 如果这个和大于等于 target，即 sums[r + 1] - sums[l] >= target，则有：sums[r+1]≥target+sums[l]
int target1 = target + sums[i - 1];
// 使用二分查找找出符合条件的前缀和位置
int bound = LowerBound(sums, i, numsLength, target1);
// 如果找到符合条件的位置，更新最小长度
if (bound != -1)
{
minLength = Math.Min(minLength, bound - i + 1);
}
}
// 如果最小长度没有更新过，返回0；否则返回最小长度
return minLength == int.MaxValue ? 0 : minLength;
}
// 辅助方法：二分查找找出数组中大于等于target的最小索引
static int LowerBound(int[] array, int left, int right, int target)
{
// 初始化中间值和原始左右边界
int mid = -1, originL = left, originR = right;
// 二分查找
while (left < right)
{
// 计算中间位置
mid = (left + right) >> 1;
// 如果中间值小于目标值，左边界右移
if (array[mid] < target) left = mid + 1;
// 否则右边界左移
else right = mid;
}
// 返回大于等于目标值的最小索引，如果没有找到，返回-1
return (array[left] >= target) ? left : -1;
}
209.3 代码
using System;
class Program
{
static void Main()
{
#region 题目
// 给定一个含有 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^9
// 1 <= nums.length <= 10^5
// 1 <= nums[i] <= 10^5
// 进阶：
// 如果你已经实现 O(n) 时间复杂度的解法, 请尝试设计一个 O(n log(n)) 时间复杂度的解法。
#endregion
#region 测试
// 示例 1
int target1 = 7;
int[] nums1 = { 2, 3, 1, 2, 4, 3 };
int result1 = MinSubArrayLen1(target1, nums1);
Console.WriteLine($"示例1 方法1 输出：{result1}");
int result1_2 = MinSubArrayLen2(target1, nums1);
Console.WriteLine($"示例1 方法2 输出：{result1_2}");
// 示例 2
int target2 = 4;
int[] nums2 = { 1, 4, 4 };
int result2 = MinSubArrayLen1(target2, nums2);
Console.WriteLine($"示例2 方法1 输出：{result2}");
int result2_2 = MinSubArrayLen2(target2, nums2);
Console.WriteLine($"示例2 方法2 输出：{result2_2}");
// 示例 3
int target3 = 11;
int[] nums3 = { 1, 1, 1, 1, 1, 1, 1, 1 };
int result3 = MinSubArrayLen1(target3, nums3);
Console.WriteLine($"示例3 方法1 输出：{result3}");
int result3_2 = MinSubArrayLen2(target3, nums3);
Console.WriteLine($"示例3 方法2 输出：{result3_2}");
#endregion
}
#region 答案
// 方法一：滑动窗口
// 使用滑动窗口来找到满足条件的最小子数组长度
static int MinSubArrayLen1(int target, int[] nums)
{
// 初始化最小长度为正无穷
int minLength = int.MaxValue;
// 初始化滑动窗口的左指针和当前窗口的总和
int left = 0, sum = 0;
// 遍历数组中的每个元素，i为滑动窗口的右指针
for (int i = 0; i < nums.Length; i++)
{
// 将当前元素加入窗口的总和
sum += nums[i];
// 当窗口内的总和大于等于目标值时，尝试收缩窗口
while (sum >= target)
{
// 更新最小长度
minLength = Math.Min(minLength, i - left + 1);
// 从窗口总和中移除最左侧的元素
sum -= nums[left];
// 将左指针右移一位
left++;
}
}
// 如果minLength没有更新过，说明没有符合条件的子数组，返回0；否则返回最小长度
return minLength == int.MaxValue ? 0 : minLength;
}
// 方法二：前缀和 + 二分查找
// 使用前缀和数组和二分查找来找到满足条件的最小子数组长度
static int MinSubArrayLen2(int target, int[] nums)
{
// 获取数组的长度
int numsLength = nums.Length;
// 如果数组为空，返回0
if (numsLength == 0)
{
return 0;
}
// 初始化最小长度为正无穷
int minLength = int.MaxValue;
// 初始化前缀和数组，长度为numsLength + 1
int[] sums = new int[numsLength + 1];
// 计算前缀和数组
for (int i = 1; i <= numsLength; ++i)
{
// 当前前缀和等于前一个前缀和加上当前元素
sums[i] = sums[i - 1] + nums[i - 1];
}
// 遍历前缀和数组
for (int i = 1; i <= numsLength; ++i)
{
// 计算目标前缀和
// 假设我们要找的子数组为 nums[l] 到 nums[r]，那么这个子数组的和为 sums[r + 1] - sums[l]。
// 如果这个和大于等于 target，即 sums[r + 1] - sums[l] >= target，则有：sums[r+1]≥target+sums[l]
int target1 = target + sums[i - 1];
// 使用二分查找找出符合条件的前缀和位置
int bound = LowerBound(sums, i, numsLength, target1);
// 如果找到符合条件的位置，更新最小长度
if (bound != -1)
{
minLength = Math.Min(minLength, bound - i + 1);
}
}
// 如果最小长度没有更新过，返回0；否则返回最小长度
return minLength == int.MaxValue ? 0 : minLength;
}
// 辅助方法：二分查找找出数组中大于等于target的最小索引
static int LowerBound(int[] array, int left, int right, int target)
{
// 初始化中间值和原始左右边界
int mid = -1, originL = left, originR = right;
// 二分查找
while (left < right)
{
// 计算中间位置
mid = (left + right) >> 1;
// 如果中间值小于目标值，左边界右移
if (array[mid] < target) left = mid + 1;
// 否则右边界左移
else right = mid;
}
// 返回大于等于目标值的最小索引，如果没有找到，返回-1
return (array[left] >= target) ? left : -1;
}
#endregion
}
209.4 运行结果
示例1 方法1 输出：2
示例1 方法2 输出：2
示例2 方法1 输出：1
示例2 方法2 输出：1
示例3 方法1 输出：0
示例3 方法2 输出：0
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 785293209@qq.com
