首页 > 编程语言 >力扣209. 长度最小的子数组C++、窗口写法

力扣209. 长度最小的子数组C++、窗口写法

时间:2024-07-23 14:24:59浏览次数:14  
标签:target nums 209 sum C++ 力扣 数组 ans 长度

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

解法一:

 

class Solution {
public:
    // 寻找最短子数组长度,其总和不小于目标值
    int minSubArrayLen(int target, vector<int>& nums) {
        int n = nums.size(); // 获取数组的长度
        if (n == 0) // 如果数组为空,则直接返回0
            return 0;
        
        int ans = INT_MAX; // 初始化最短子数组长度为最大整数
        vector<int> sums(n + 1, 0); // 创建一个大小为n+1的数组,用于存储前i个元素的和
        
        // 计算前i个元素的和
        for (int i = 1; i <= n; i++) {
            sums[i] = sums[i - 1] + nums[i - 1];
        }
        
        // 遍历每个位置,查找以当前位置开始的满足条件的子数组
        for (int i = 1; i <= n; i++) {
            // 计算当前位置及之前元素的和加上目标值
            int s = sums[i - 1] + target;
            // 使用lower_bound在sums数组中查找大于等于s的第一个元素的位置
            auto bound = lower_bound(sums.begin(), sums.end(), s);
            // 如果找到这样的位置,更新最短子数组长度
            if (bound != sums.end()) {
                ans = min(ans, static_cast<int>(bound - sums.begin()) - i + 1);
            }
        }
        // 如果最短子数组长度没有改变,则返回0,表示找不到符合条件的子数组
        return ans == INT_MAX ? 0 : ans;
    }
};

 

解法思路:

  1. 首先判断输入的数组是否为空,如果为空,则直接返回0。
  2. 定义一个变量ans,用于存储最小子数组的长度。初始值设为INT_MAX,表示一个无穷大的值。
  3. 定义一个长度为n+1的数组sums,用于存储nums数组的前缀和。sums[i]表示nums数组中前i个元素的和。
  4. 遍历nums数组,计算sums数组的前缀和。
  5. 遍历nums数组,对于每个元素nums[i],计算目标和s=sums[i-1]+target。
  6. 使用lower_bound函数在sums数组中查找大于等于s的元素的位置,得到指向该位置的迭代器bound。
  7. 如果找到了这样的位置,则计算子数组的长度ans,并更新ans的最小值。
  8. 返回ans的值,如果ans仍然为INT_MAX,则说明没有找到满足条件的子数组,返回0。

解法二:窗口 

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int n = nums.size(); // 数组长度
        if (n == 0) // 如果数组为空,直接返回0
            return 0;
        int ans = INT_MAX; // 最小子数组长度,初始值设为INT_MAX,表示一个无穷大的值
        int sum = 0, start = 0; // 子数组的和sum和起始位置start

        // 遍历数组
        for (int end = 0; end < n; end++) {
            sum += nums[end]; // 计算当前子数组的和

            // 如果子数组的和sum大于等于目标值target,进入循环
            while (sum >= target) {
                ans = min(ans, end - start + 1); // 更新最小子数组长度

                sum -= nums[start]; // 从子数组中减去起始位置元素的值
                start++; // 起始位置向右移动一位,相当于缩短了子数组的长度
            }
        }

        return ans == INT_MAX ? 0 : ans; // 返回最小子数组长度,如果ans仍然为INT_MAX,则说明没有找到满足条件的子数组,返回0
    }
};
 

这个窗口的解题思路是通过两个指针start和end来构建一个滑动窗口,窗口的左边界是start,右边界是end。初始时,start和end都指向数组的第一个元素。

在遍历数组的过程中,不断移动end指针,将当前元素加入窗口的和sum中。如果sum大于等于目标值target,则进入循环。

在循环中,先计算当前子数组的长度(end - start + 1),并将其与之前的最小子数组长度ans进行比较,保留较小的值。接着,从窗口中减去起始位置元素的值,即sum -= nums[start],然后将start指针向右移动一位,相当于缩短了窗口的长度。

接着再次判断sum是否大于等于target,并重复上述过程,直到窗口中的和sum小于目标值target。然后继续移动end指针,将下一个元素加入窗口,并再次重复上述过程。

最终,当整个数组遍历完毕后,返回最小子数组长度ans。如果ans仍然为INT_MAX,则说明没有找到满足条件的子数组,返回0。

标签:target,nums,209,sum,C++,力扣,数组,ans,长度
From: https://blog.csdn.net/2301_80345285/article/details/140633337

相关文章

  • 力扣68. 文本左右对齐
    给定一个单词数组 words 和一个长度 maxWidth ,重新排版单词,使其成为每行恰好有 maxWidth 个字符,且左右两端对齐的文本。你应该使用“贪心算法”来放置给定的单词;也就是说,尽可能多地往每行中放置单词。必要时可用空格 '' 填充,使得每行恰好有 maxWidth 个字符。要......
  • 三种语言实现快速选择(C++/Python/Java)
    题目给定一个长度为......
  • C++11 智能指针之shared_ptr
    1.背景基于Alexa的全链路智能语音SDK基于C++实现了跨平台特性,跑通了Android、Mac、Linux等设备,在兼容iOS时发现iOS未提供音频采集和播放的C++接口,所以需要改造SDK,允许SDK初始化时注入外部的采集器和播放器实现类,同时SDK中的Android播放器是基于ffmpeg解码+opensl实现,但......
  • C++11 智能指针之shared_from_this
    shared_ptr作用:C++中采用new和delete来申请和释放内存,如果管理不当,很容易出现内存泄露;std::shared_ptr,std::unique_ptr,std::weak_ptr,三种智能指针类,可以自动管理内存使用示例:智能指针对象和一般的指针用法几乎完全相同#include<iostream>#include<memory>//需......
  • C++多线程并发基础入门教程
    C++多线程并发基础入门教程《C++ConcurrencyinAction,SecondEdition》这本书深入浅出的讲解了C++多线程知识;如果英文水平足够好,可以查阅英文原版,它也有中文译本,虽然翻译过来的质量不如原版,但英文原版阅读太费精力;我推荐新手或者有一定经验的人看这本书。1什么是C++多......
  • Qt与C++标准的兼容之旅
    第一章:Qt与C++:相互成就的技术演进Qt,作为一个跨平台的应用程序和用户界面框架,自其诞生之初便与C++紧密相连。C++,一种广泛使用的高级编程语言,以其高效的性能和面向对象的特性在软件开发中占据重要地位。在探讨Qt与C++之间的关系时,我们不仅是在分析技术层面的互动,更是在审视一......
  • C++数据类型
    基本数据类型(PrimitiveDataTypes)整数类型(IntegerTypes)int:用于表示整数,大小通常为4字节(32位),范围约为-2,147,483,648到2,147,483,647。inta=10;short:表示较小的整数,通常为2字节(16位),范围约为-32,768到32,767。shortb=100;long:表示较大的整数,通......
  • C++STL
    C++标准模板库(StandardTemplateLibrary,STL)是一套功能强大的C++模板类和函数的集合,它提供了一系列通用的、可复用的算法和数据结构。STL的设计基于泛型编程,这意味着使用模板可以编写出独立于任何特定数据类型的代码。泛型编程:不使用具体数据类型(int、double、float等),而是使......
  • C++ 特殊成员函数的注意事项
    在C++中,特殊成员函数指的是编译器在某些特定情况下会自动生成的成员函数,包括默认构造函数、析构函数、拷贝构造函数、拷贝赋值运算符、移动构造函数和移动赋值运算符。了解并正确使用这些特殊成员函数对于编写高效、可维护的C++代码至关重要。以下是一些关于这些特殊成员函数......
  • 力扣题库合集(2):动态规划(1)
      本文将持续更新~~ hellohello~,这里是绝命Coding——老白~......