What defines a good subarray in Maximum Good Subarray Sum?

A good subarray has its first and last elements differ by exactly k, meaning |nums[i] - nums[j]| == k.

Can the array contain negative numbers?

Yes, nums[i] can be negative, and prefix sums must account for them when calculating maximum subarray sums.

How does GhostInterview use hash maps in this problem?

It stores prefix sums keyed by element values to quickly find potential subarrays with the correct difference k.

What happens if there are no good subarrays?

The correct return value is 0, as no subarray meets the difference condition.

Is it necessary to check every subarray combination?

No, by scanning once and using prefix sums with a hash map, all candidate subarrays are efficiently evaluated without nested loops.

#3026

Medium

auto_awesome数组·哈希·扫描

LeetCode 题解工作台

最大好子数组和

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

数组哈希表前缀和

题目描述

给你一个长度为 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 <= 10⁵
-10⁹ <= nums[i] <= 10⁹
1 <= k <= 10⁹

lightbulb

解题思路

方法一：前缀和 + 哈希表

我们用一个哈希表 $p$ 记录 $nums[i]$ 的前缀数组 $nums[0..i-1]$ 的和 $s$ ，如果有多个相同的 $nums[i]$ ，我们只保留最小的 $s$ 。初始时，我们将 $p[nums[0]]$ 设为 $0$ 。另外，我们用一个变量 $s$ 记录当前的前缀和，初始时 $s = 0$ 。初始化答案 $ans$ 为 $-\infty$ 。

接下来，我们枚举 $nums[i]$ ，并且维护一个变量 $s$ 表示 $nums[0..i]$ 的和。如果 $nums[i] - k$ 在 $p$ 中，那么我们就找到了一个好子数组，将答案更新为 $ans = \max(ans, s - p[nums[i] - k])$ 。同理，如果 $nums[i] + k$ 在 $p$ 中，那么我们也找到了一个好子数组，将答案更新为 $ans = \max(ans, s - p[nums[i] + k])$ 。然后，如果 $i + 1 \lt n$ 并且 $nums[i + 1]$ 不在 $p$ 中，或者 $p[nums[i + 1]] \gt s$ ，我们就将 $p[nums[i + 1]]$ 设为 $s$ 。

最后，如果 $ans = -\infty$ ，那么我们返回 $0$ ，否则返回 $ans$ 。

时间复杂度 $O(n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 是数组的长度。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

class Solution:
    def maximumSubarraySum(self, nums: List[int], k: int) -> int:
        ans = -inf
        p = {nums[0]: 0}
        s, n = 0, len(nums)
        for i, x in enumerate(nums):
            s += x
            if x - k in p:
                ans = max(ans, s - p[x - k])
            if x + k in p:
                ans = max(ans, s - p[x + k])
            if i + 1 < n and (nums[i + 1] not in p or p[nums[i + 1]] > s):
                p[nums[i + 1]] = s
        return 0 if ans == -inf else ans

speed

复杂度分析

指标	值
时间	complexity is O(n) since each element is processed once and hash lookups are O(1). Space complexity is O(n) for storing prefix sums and hash map entries.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Checks if you understand prefix sums and hash table usage for subarray problems.
question_mark
Wants to see how you optimize scanning large arrays without nested loops.
question_mark
Assesses whether you handle negative numbers and zero-length edge cases properly.

warning

常见陷阱

外企场景

error
Recomputing subarray sums naively instead of using prefix sums causes timeouts.
error
Forgetting to handle negative numbers can lead to incorrect maximum sums.
error
Not checking both +k and -k differences when searching in the hash map.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Find minimum sum of good subarrays instead of maximum.
arrow_right_alt
Return the number of good subarrays that meet the k difference condition.
arrow_right_alt
Modify k dynamically based on subarray length or value ranges.

help

常见问题

外企场景

继续练习

#2875 无限数组的最短子数组 #2848 与车相交的点 #2845 统计趣味子数组的数目