18

leetcode1546题解【前缀和+贪心】

 3 years ago
source link: http://www.cnblogs.com/KeepZ/p/13698826.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.

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;
    }
};

report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK