力扣3026.最大好子数组和
-
一次遍历
- 求前缀和的同时 哈希表key为元素值 value为前缀和
- 始终保证cnt[key]的前缀和最小
-
class Solution { public: long long maximumSubarraySum(vector<int>& nums, int k) { long long res = LLONG_MIN , sum = 0; unordered_map<int,long long> min_s; for(int x : nums) { //找x + k的位置 auto it = min_s.find(x + k); if(it != min_s.end()) res = max(res,sum + x - it->second); //找x - k的位置 it = min_s.find(x - k); if(it != min_s.end()) res = max(res,sum + x - it->second); //找x的位置 it = min_s.find(x); if(it == min_s.end() || sum < it->second) min_s[x] = sum; //求当前遍历过元素的和 sum += x; } return res == LLONG_MIN ? 0 : res; } };