leetcode1546题解【前缀和+贪心】
2024-08-27 12:51:15
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;
}
};
最新文章
- CSS3 新怎的伪类选择器
- vs快捷方式
- svn下目录说明
- 安装Arch Linux(桌面环境)
- 最简单例子图解JVM内存分配和回收
- JavaScript 判断用户输入的邮箱及手机格式是否正确
- MongoDB学习笔记06
- poj 1077-Eight(八数码+逆向bfs打表)
- Windows常用的监视数据指标
- Qt实现QQ界面
- C#基础语法
- 【Java基础】【03运算符&;if语句】
- Python 字节流写入文件
- Hadoop记录-fair公平调度队列管理
- UOJ67 新年的毒瘤 tarjan
- pd.concat/merge/join
- 【Spring Security】六、自定义认证处理的过滤器
- 套接字编程,建立连接connect,绑定套接字bind
- 常见异常代码oracle
- JavaScript有关的10个怪癖和秘密(转)