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;
}
};
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/89015.html
標籤：其他