专栏首页用户6093955的专栏leetcode1546题解【前缀和+贪心】

leetcode1546题解【前缀和+贪心】

leetcode1546.和为目标值的最大数目不重叠非空子数组数目

题目链接

算法

前缀和+贪心

时间复杂度O(n)。

1.对nums数组求前缀和;

2.在求前缀和过程中将前缀和sum插入到set集合中,每次都在set集合中寻找sum-target是否存在,如果存在,说明存在这么一个子数组,满足该子数组中的数字和等于target;

3.在set集合中找到sum-target后,就记录一次,同时需要将sum清零并且将set集合清空,目的是让符合条件的子数组不重叠。

C++代码

class Solution {
public:
    int maxNonOverlapping(vector<int>& nums, int target) {
        int len = nums.size();
        int sum = 0, res = 0;
        set<int> hs;    //记录前缀和
        hs.insert(0);
        for(int i = 0; i < len; i++){
            sum += nums[i];
            if(hs.find(sum - target) != hs.end()){
                sum = 0;
                hs.clear();     //为了不让子数组重叠,需要清空数组
                res++;  
            }   
            hs.insert(sum);
        }
        return res;
    }
};

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 【lower_bound、upperbound讲解、二分查找、最长上升子序列(LIS)模版】

    注意此模板只适用于查找a中是否存在v,存在的话则返回其中一个符合条件的位置,并不一定只有那一个位置,这个视情况而定。

    _DIY
  • CF: Long Number

    分析1:题目原文中有这么一句“You can perform the following operation no more than once: choose...

    _DIY
  • 走迷宫(bfs, 最短路)

    _DIY
  • 装服务器偶得

    happy123.me
  • Android BitmapUtils工具类使用详解

    本文实例为大家分享了Android BitmapUtils工具类的具体代码,供大家参考,具体内容如下

    砸漏
  • 如何在Ubuntu 14.04上使用MySQL或MariaDB和Django应用程序

    Django是一个用于快速创建Python应用程序的灵活框架。默认情况下,Django应用程序配置为将数据存储到轻量级SQLite数据库文件中。虽然这在某些负载...

    苏子晨
  • 局域网内利用gitlab,jenkins自动生成gitbook并发布(nginx)

    基本的流程是这样的,每本书作为项目托管到gitlab上,每次提交,gitlab会触发jenkins,jenkins会把仓库的内容拉下来,gitbook buil...

    zqb_all
  • 如何在CentOS 7上使用Django应用程序使用MariaDB

    Django是一个用于快速创建Python应用程序的灵活框架。默认情况下,Django应用程序配置为将数据存储到轻量级SQLite数据库文件中。虽然这在某些负载...

    你在哪里
  • 数据库缓存最终一致性的四种方案

    原文链接:https://juejin.im/post/5d5c99b66fb9a06ae072060d

    业余草
  • 压榨、被套路 渠道商的出路何在?

    人称T客

扫码关注云+社区

领取腾讯云代金券