题目描述
给你一个长度为 n
的数组 nums
和一个 正 整数 k
。
如果 nums
的一个子数组中,第一个元素和最后一个元素 差的绝对值恰好 为 k
,我们称这个子数组为 好 的。换句话说,如果子数组 nums[i..j]
满足 |nums[i] - nums[j]| == k
,那么它是一个好子数组。
请你返回 nums
中 好 子数组的 最大 和,如果没有好子数组,返回 0
。
样例
输入:nums = [1,2,3,4,5,6], k = 1
输出:11
解释:好子数组中第一个元素和最后一个元素的差的绝对值必须为 1。
好子数组有 [1,2],[2,3],[3,4],[4,5] 和 [5,6]。
最大子数组和为 11,对应的子数组为 [5,6]。
输入:nums = [-1,3,2,4,5], k = 3
输出:11
解释:好子数组中第一个元素和最后一个元素的差的绝对值必须为 3。
好子数组有 [-1,3,2] 和 [2,4,5]。
最大子数组和为 11,对应的子数组为 [2,4,5]。
输入:nums = [-1,-2,-3,-4], k = 2
输出:-6
解释:好子数组中第一个元素和最后一个元素的差的绝对值必须为 2。
好子数组有 [-1,-2,-3] 和 [-2,-3,-4]。
最大子数组和为 -6,对应的子数组为 [-1,-2,-3]。
限制
2 <= nums.length <= 10^5
-10^9 <= nums[i] <= 10^9
1 <= k <= 10^9
算法
(哈希表,前缀和) $O(n)$
- 定义一个哈希表 $h$,其中 $h(i)$ 表示当前元素的值为 $i$ 时,其前缀和(不包含 $i$)的最小值。
- 遍历数组,对于当前元素 $x$ 和之前的前缀和 $sum$,在哈希表中寻找 $h(x + k)$ 和 $h(x - k)$,如果存在,则更新答案。
- 然后更新哈希表,和前缀和 $sum$。
时间复杂度
- 遍历数组一次,每次操作和查询哈希表仅需要常数的时间,故总时间复杂度为 $O(n)$。
空间复杂度
- 需要 $O(n)$ 的额外空间存储哈希表。
C++ 代码
#define LL long long
class Solution {
public:
LL maximumSubarraySum(vector<int>& nums, int k) {
const int n = nums.size();
unordered_map<int, LL> h;
LL sum = 0, ans = INT64_MIN;
for (int x : nums) {
if (h.count(x + k))
ans = max(ans, sum + x - h[x + k]);
if (h.count(x - k))
ans = max(ans, sum + x - h[x - k]);
if (h.count(x)) h[x] = min(h[x], sum);
else h[x] = sum;
sum += x;
}
if (ans == INT64_MIN)
return 0;
return ans;
}
};