7. 3026.最大好子數組和(中等,學習)

3026. 最大好子數組和 - 力扣（LeetCode）

思想

1.給你一個長度為 n 的數組 nums 和一個 正 整數 k 。
如果 nums 的一個子數組中，第一個元素和最后一個元素 差的絕對值恰好 為 k ，我們稱這個子數組為 好 的。換句話說，如果子數組 nums[i..j] 滿足 |nums[i] - nums[j]| == k ，那么它是一個好子數組。
請你返回 nums 中 好 子數組的 最大 和，如果沒有好子數組，返回 0 。
2.此題|nums[i] - nums[j]| == k,既可以枚舉nums[j],尋找nums[j]+k和nums[j]-k,所以哈希表的鍵為nums[j].要讓s[j+1]-s[i]最大，此時s[j+1]是固定的，所以要讓s[i]最小，所以哈希表的值為同一個nums[i]下最小的s[i](不包括nums[i],所以先更新哈希表再更新s)(學習如何確定的思想)

代碼

c++:

class Solution {
public:long long maximumSubarraySum(vector<int>& nums, int k) {int n = nums.size();vector<long long> s(n + 1);s[0] = 0;for (int i = 0; i < n; ++i)s[i + 1] = s[i] + nums[i];long long res = LONG_MIN;map<int, long long> mp; // nums[i]-相同nums[i]下s[i]的最小值for (int j = 0; j < n; ++j) {auto it1 = mp.find(nums[j] + k);auto it2 = mp.find(nums[j] - k);if (it1 != mp.end())res = max(res, s[j + 1] - it1->second);if (it2 != mp.end())res = max(res, s[j + 1] - it2->second);auto it3 = mp.find(nums[j]);if (it3 == mp.end() || s[j] < it3->second)mp[nums[j]] = s[j];}if (res == LONG_MIN)return 0;return res;}
};

優化成一個變量,先更新哈希表再更新s

class Solution {
public:long long maximumSubarraySum(vector<int>& nums, int k) {int n = nums.size();long long s = 0;long long res = LONG_MIN;map<int, long long>mp; // nums[i]-相同nums[i]下s[i]的最小值(此時的nums[i]不包括nums[i],所以先更新哈希表再更新s)for (auto& x : nums) {auto it1 = mp.find(x + k);auto it2 = mp.find(x - k);if (it1 != mp.end())res = max(res, s + x - it1->second);if (it2 != mp.end())res = max(res, s + x - it2->second);auto it3 = mp.find(x);// 先不包括nums[i]if (it3 == mp.end() || s < it3->second)mp[x] = s;s += x;}if (res == LONG_MIN)return 0;return res;}
};

8. 1477.找兩個和為目標值且不重疊的子數組(中等,動態規劃，之后再做)

1477. 找兩個和為目標值且不重疊的子數組 - 力扣（LeetCode）

思想

代碼

c++:

9. 1546.和為目標值且不重疊的非空子數組的最大數目(中等,細節處理)

1546. 和為目標值且不重疊的非空子數組的最大數目 - 力扣（LeetCode）

思想

1.給你一個數組 nums 和一個整數 target 。
請你返回 非空不重疊 子數組的最大數目，且每個子數組中數字和都為 target 。
2.思路沒有問題，對于區間[l,r),要讓s[r]-s[l]=target,即s[l]=s[r]-target,所以哈希表的鍵為s[r],因為要不重疊，所以采取貪心思想，記錄前一個區間的右開端點end,哈希表的值為閉端點下標,此時的區間[it->second,i)

代碼

c++:

class Solution {
public:int maxNonOverlapping(vector<int>& nums, int target) {int n = nums.size();int s = 0;map<int, int> mp; // s[i]-imp[0] = 0;int cnt = 0;int end = -1;for (int i = 1; i <= n; ++i) {s += nums[i - 1]; // s[i]auto it = mp.find(s - target);if (it != mp.end()) {// [,end)與[it->second,i)不重疊if (end <= it->second) {++cnt;end = i;}}mp[s] = i;}return cnt;}
};

10. 1124.表現良好的最長時間段(中等,單調棧待學習)

1124. 表現良好的最長時間段 - 力扣（LeetCode）

思想

代碼

c++:

11. 3381.長度可被K整除的子數組的最大元素和(中等,學習)

3381. 長度可被 K 整除的子數組的最大元素和 - 力扣（LeetCode）

思想

1.給你一個整數數組 nums 和一個整數 k 。
返回 nums 中一個 非空子數組 的 最大 和，要求該子數組的長度可以 被 k 整除。
2.區間[l,r),即(r-l)%k=0,即r%k=l%k,所以哈希表的鍵為j%k,要讓s[r]-s[l]最大，所以哈希表的值為min(s[i]),遍歷前綴和數組，先更新答案，再更新哈希表，因為是取余，所以可以開長度為k的數組，初始值為LLONG_MAX/2,防止減法溢出

代碼

c++:

class Solution {
public:long long maxSubarraySum(vector<int>& nums, int k) {int n=nums.size();vector<long long> s(n+1);for(int i=0;i<n;++i)    s[i+1]=s[i]+nums[i];long long res=LLONG_MIN;vector<long long> minS(k,LLONG_MAX/2);// 遍歷前綴和數組for(int j=0;j<=n;++j){int mod=j%k;res=max(res,s[j]-minS[mod]);minS[mod]=min(minS[mod],s[j]);}return res;}
};
\*map<int,long long> mp;// 遍歷前綴和數組for (int j = 0; j <= n; ++j) {int mod = j % k;auto it=mp.find(mod);if(it!=mp.end()){res=max(res,s[j]-it->second);}if(it==mp.end() || s[j]<it->second) mp[mod]=s[j];}
*\

單變量s優化:

class Solution {
public:long long maxSubarraySum(vector<int>& nums, int k) {int n = nums.size();long long s = 0;long long res = LLONG_MIN;map<int, long long> mp; // 下標-值mp[k - 1] = 0;          // 前綴和第一個元素為0，下標為-1，取余k為k-1for (int j = 0; j < n; ++j) {s += nums[j];int mod = j % k;auto it = mp.find(mod);if (it != mp.end()) {res = max(res, s - it->second);}if (it == mp.end() || s < it->second)mp[mod] = s;}return res;}
};