209.长度最小的子数组

LeetCode LeetCode 数组 前缀和 二分查找 滑动窗口
发布时间 :
字数:2.1k 阅读 : 评论:
  1. 209.长度最小的子数组
    1. 209.1 题目
    2. 209.2 题解
      1. 滑动窗口
      2. 前缀和 + 二分查找
    3. 209.3 代码
    4. 209.4 运行结果

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^9
  • 1 <= nums.length <= 10^5
  • 1 <= 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

赏

©2016-2024 Tao

Built with Hexo and 3-hexo theme

×

喜欢就点赞,疼爱就打赏