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]。子数组 [5,6] 的最大和为 11。

示例 2：

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

示例 3：

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

提示：

  • 2 <= nums.length <= 10^5
  • -10^9 <= nums[i] <= 10^9
  • 1 <= k <= 10^9

解题思路

这道题要求找到满足首尾元素绝对差值为 k 的子数组的最大和。我们可以使用前缀和配合哈希表来高效解决。

核心思路：

  1. 使用前缀和技巧，将子数组和的计算转化为两个前缀和的差值
  2. 对于每个位置 i，我们想找到之前的某个位置 j，使得 |nums[i] - nums[j]| = k
  3. 这意味着 nums[j] = nums[i] + k 或 nums[j] = nums[i] - k
  4. 使用哈希表存储每个数值对应的最小前缀和（为了最大化子数组和）

算法步骤：

  1. 遍历数组，维护当前前缀和
  2. 对于当前元素 nums[i]，在哈希表中查找 nums[i] + k 和 nums[i] - k
  3. 如果找到，计算对应的子数组和并更新最大值
  4. 将当前元素及其对应的最小前缀和存入哈希表

优化细节：

  • 哈希表中存储的是到达某个值时的最小前缀和，这样能保证计算出的子数组和最大
  • 需要特别处理边界情况，确保子数组至少包含两个元素

代码实现

class Solution {
public:
    long long maximumSubarraySum(vector<int>& nums, int k) {
        unordered_map<int, long long> minPrefixSum;
        long long prefixSum = 0;
        long long result = LLONG_MIN;
        bool found = false;
        
        for (int i = 0; i < nums.size(); i++) {
            prefixSum += nums[i];
            
            // 查找 nums[i] - k 和 nums[i] + k
            if (minPrefixSum.find(nums[i] - k) != minPrefixSum.end()) {
                result = max(result, prefixSum - minPrefixSum[nums[i] - k]);
                found = true;
            }
            if (minPrefixSum.find(nums[i] + k) != minPrefixSum.end()) {
                result = max(result, prefixSum - minPrefixSum[nums[i] + k]);
                found = true;
            }
            
            // 更新当前数字对应的最小前缀和
            long long prevPrefixSum = prefixSum - nums[i];
            if (minPrefixSum.find(nums[i]) == minPrefixSum.end() || 
                minPrefixSum[nums[i]] > prevPrefixSum) {
                minPrefixSum[nums[i]] = prevPrefixSum;
            }
        }
        
        return found ? result : 0;
    }
};

class Solution:
    def maximumSubarraySum(self, nums: List[int], k: int) -> int:
        min_prefix_sum = {}
        prefix_sum = 0
        result = float('-inf')
        found = False
        
        for i in range(len(nums)):
            prefix_sum += nums[i]
            
            # 查找 nums[i] - k 和 nums[i] + k
            if nums[i] - k in min_prefix_sum:
                result = max(result, prefix_sum - min_prefix_sum[nums[i] - k])
                found = True
            if nums[i] + k in min_prefix_sum:
                result = max(result, prefix_sum - min_prefix_sum[nums[i] + k])
                found = True
            
            # 更新当前数字对应的最小前缀和
            prev_prefix_sum = prefix_sum - nums[i]
            if nums[i] not in min_prefix_sum or min_prefix_sum[nums[i]] > prev_prefix_sum:
                min_prefix_sum[nums[i]] = prev_prefix_sum
        
        return result if found else 0

public class Solution {
    public long MaximumSubarraySum(int[] nums, int k) {
        Dictionary<int, long> minPrefixSum = new Dictionary<int, long>();
        long prefixSum = 0;
        long result = long.MinValue;
        bool found = false;
        
        for (int i = 0; i < nums.Length; i++) {
            prefixSum += nums[i];
            
            // 查找 nums[i] - k 和 nums[i] + k
            if (minPrefixSum.ContainsKey(nums[i] - k)) {
                result = Math.Max(result, prefixSum - minPrefixSum[nums[i] - k]);
                found = true;
            }
            if (minPrefixSum.ContainsKey(nums[i] + k)) {
                result = Math.Max(result, prefixSum - minPrefixSum[nums[i] + k]);
                found = true;
            }
            
            // 更新当前数字对应的最小前缀和
            long prevPrefixSum = prefixSum - nums[i];
            if (!minPrefixSum.ContainsKey(nums[i]) || minPrefixSum[nums[i]] > prevPrefixSum) {
                minPrefixSum[nums[i]] = prevPrefixSum;
            }
        }
        
        return found ? result : 0;
    }
}

var maximumSubarraySum = function(nums, k) {
    const minPrefixSum = new Map();
    let prefixSum = 0;
    let result = -Infinity;
    let found = false;
    
    for (let i = 0; i < nums.length; i++) {
        prefixSum += nums[i];
        
        // 查找 nums[i] - k 和 nums[i] + k
        if (minPrefixSum.has(nums[i] - k)) {
            result = Math.max(result, prefixSum - minPrefixSum.get(nums[i] - k));
            found = true;
        }
        if (minPrefixSum.has(nums[i] + k)) {
            result = Math.max(result, prefixSum - minPrefixSum.get(nums[i] + k));
            found = true;
        }
        
        // 更新当前数字对应的最小前缀和
        const prevPrefixSum = prefixSum - nums[i];
        if (!minPrefixSum.has(nums[i]) || minPrefixSum.get(nums[i]) > prevPrefixSum) {
            minPrefixSum.set(nums[i], prevPrefixSum);
        }
    }
    
    return found ? result : 0;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(n) - 只需遍历数组一次，哈希表操作均为 O(1)
空间复杂度O(n) - 哈希表最多存储 n 个不同的数值

相关题目