最大好子数组和

标签: 数组 哈希表 前缀和

难度: Medium

给你一个长度为 n 的数组 nums 和一个 正 整数 k 。

如果 nums 的一个子数组中，第一个元素和最后一个元素 差的绝对值恰好 为 k ，我们称这个子数组为 好 的。换句话说，如果子数组 nums[i..j] 满足 |nums[i] - nums[j]| == k ，那么它是一个好子数组。

请你返回 nums 中 好 子数组的 最大 和，如果没有好子数组，返回 0 。

示例 1：

输入：nums = [1,2,3,4,5,6], k = 1
输出：11
解释：好子数组中第一个元素和最后一个元素的差的绝对值必须为 1 。好子数组有 [1,2] ，[2,3] ，[3,4] ，[4,5] 和 [5,6] 。最大子数组和为 11 ，对应的子数组为 [5,6] 。

示例 2：

输入：nums = [-1,3,2,4,5], k = 3
输出：11
解释：好子数组中第一个元素和最后一个元素的差的绝对值必须为 3 。好子数组有 [-1,3,2] 和 [2,4,5] 。最大子数组和为 11 ，对应的子数组为 [2,4,5] 。

示例 3：

输入：nums = [-1,-2,-3,-4], k = 2
输出：-6
解释：好子数组中第一个元素和最后一个元素的差的绝对值必须为 2 。好子数组有 [-1,-2,-3] 和 [-2,-3,-4] 。最大子数组和为 -6 ，对应的子数组为 [-1,-2,-3] 。

提示：

  • 2 <= nums.length <= 105
  • -109 <= nums[i] <= 109
  • 1 <= k <= 109

Submission

运行时间: 183 ms

内存: 28.5 MB

# https://leetcode.cn/u/l00/

# class Solution:
#     def maximumSubarraySum(self, nums: List[int], k: int) -> int:
#         dic = defaultdict(lambda :inf)
#         preSum = 0
#         ans = -inf
#         for num in nums:
#             if preSum < dic[num]: dic[num] = preSum
#             preSum += num
#             if num - k in dic and preSum - dic[num - k] > ans: ans = preSum - dic[num - k]
#             if num + k in dic and preSum - dic[num + k] > ans: ans = preSum - dic[num + k]
#         return 0 if ans == -inf else ans

class Solution:
    def maximumSubarraySum(self, nums: List[int], k: int) -> int:
        dic = {}
        preSum = 0
        ans = -inf
        for num in nums:
            if not num in dic or preSum < dic[num]: dic[num] = preSum
            preSum += num
            if num - k in dic and preSum - dic[num - k] > ans: ans = preSum - dic[num - k]
            if num + k in dic and preSum - dic[num + k] > ans: ans = preSum - dic[num + k]
        return 0 if ans == -inf else ans

Explain

这个解决方案利用了前缀和和哈希表来查找符合条件的子数组和其最大和。前缀和用于计算从数组开始到当前位置的元素和，而哈希表用来存储每个遇到的元素的最小前缀和。对于数组中的每个元素，我们检查这个元素减去k以及加上k的值是否存在于哈希表中。如果存在，我们通过当前的前缀和减去哈希表中存储的前缀和，来计算可能的好子数组的和，并更新最大和。这样做可以有效地在一次遍历中找到满足条件的子数组并计算其和。

时间复杂度: O(n)

空间复杂度: O(n)

# class Solution:
#     def maximumSubarraySum(self, nums: List[int], k: int) -> int:
#         dic = {}  # 初始化空哈希表
#         preSum = 0  # 初始化前缀和为0
#         ans = -inf  # 初始化最大和为负无穷大，处理所有子数组和都小于0的情况
#         for num in nums:  # 遍历每个元素
#             if not num in dic or preSum < dic[num]: dic[num] = preSum  # 更新当前元素的最小前缀和
#             preSum += num  # 更新前缀和
#             if num - k in dic and preSum - dic[num - k] > ans: ans = preSum - dic[num - k]  # 检查是否有符合条件的好子数组，并更新最大和
#             if num + k in dic and preSum - dic[num + k] > ans: ans = preSum - dic[num + k]  # 检查是否有符合条件的好子数组，并更新最大和
#         return 0 if ans == -inf else ans  # 如果没有找到任何好子数组，返回0，否则返回最大和

Explore

是的，这个方法可以处理所有元素都是负数的情况。因为无论元素的符号如何，哈希表存储的是到当前元素为止的最小前缀和，这有助于计算任何子数组的和。在负数的情况下，最小前缀和将帮助我们找到可能的最大子数组和，因为从较小的负数前缀和到当前的前缀和的差值会较大，这正是我们想要最大化的值。

是的，算法仍然有效，即使数组中有重复元素。算法使用哈希表存储每个元素值对应的最小前缀和，并在遍历过程中不断更新它。如果数组中有重复的元素，算法会考虑到每个重复元素的情况，并在计算子数组和时考虑到所有符合条件的子数组。因此，算法可以准确地计算出最大的子数组和，无论数组中是否包含重复元素。

选择更新元素的最小前缀和而不是最大前缀和，是因为这样可以更有效地找到最大的子数组和。子数组的和可以通过当前前缀和减去之前的某个前缀和来计算。如果我们使用最小前缀和，那么当前前缀和减去最小前缀和将会给出可能的最大子数组和。反之，如果我们存储的是最大前缀和，那么计算出的子数组和会较小，无法达到寻找最大子数组和的目的。

实际上，如果`num - k`或`num + k`不在哈希表中，那么说明到目前为止还没有遇到能使得子数组和为k的元素。这意味着之前的元素和当前元素的组合不能形成好子数组。算法通过持续更新哈希表并检查每个元素时的条件来确保不遗漏任何可能的好子数组。虽然在某些情况下，初次遇到的`num - k`或`num + k`可能不在哈希表中，但这并不影响算法的有效性，因为对于每个新元素，只有在其相对应的`num - k`或`num + k`已经存在于哈希表中时，才可能形成好子数组。