Medium

题目描述

给你一个整数数组 nums 和一个整数 k。找出所有满足以下条件的 nums 子数组的最大子数组和：

  • 子数组的长度是 k，且
  • 子数组中的所有元素都不相同。

返回满足条件的所有子数组的最大子数组和。如果没有子数组满足条件，返回 0。

子数组是数组中一个连续的非空元素序列。

示例 1：

输入：nums = [1,5,4,2,9,9,9], k = 3
输出：15
解释：长度为 3 的 nums 子数组为：
- [1,5,4] 满足要求，和为 10。
- [5,4,2] 满足要求，和为 11。
- [4,2,9] 满足要求，和为 15。
- [2,9,9] 不满足要求，因为元素 9 重复了。
- [9,9,9] 不满足要求，因为元素 9 重复了。
我们返回 15，因为它是满足条件的所有子数组中的最大子数组和。

示例 2：

输入：nums = [4,4,4], k = 3
输出：0
解释：长度为 3 的 nums 子数组为：
- [4,4,4] 不满足要求，因为元素 4 重复了。
我们返回 0，因为没有子数组满足条件。

约束条件：

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

解题思路

这是一道典型的滑动窗口问题，需要维护一个长度为 k 的窗口，并检查窗口内元素是否都不相同。

解题思路

方法一：滑动窗口 + 哈希表（推荐）

  1. 使用滑动窗口技术，维护一个大小为 k 的窗口
  2. 用哈希表记录窗口内每个元素的频次
  3. 用一个变量记录当前窗口的和
  4. 当窗口大小达到 k 时：
    • 检查窗口内是否所有元素都不重复（哈希表大小等于 k）
    • 如果满足条件，更新最大和
    • 移除窗口左端元素，为下次迭代做准备

优化点：

  • 使用频次计数而不是集合，能更高效地处理元素的添加和删除
  • 维护窗口和，避免每次重新计算

时间复杂度为 O(n)，空间复杂度为 O(k)，其中 n 是数组长度。每个元素最多被访问两次（加入和移出窗口各一次）。

代码实现

class Solution {
public:
    long long maximumSubarraySum(vector<int>& nums, int k) {
        int n = nums.size();
        unordered_map<int, int> freq;
        long long currentSum = 0;
        long long maxSum = 0;
        
        for (int i = 0; i < n; i++) {
            // 添加当前元素到窗口
            freq[nums[i]]++;
            currentSum += nums[i];
            
            // 如果窗口大小超过k，移除左端元素
            if (i >= k) {
                int leftElement = nums[i - k];
                freq[leftElement]--;
                if (freq[leftElement] == 0) {
                    freq.erase(leftElement);
                }
                currentSum -= leftElement;
            }
            
            // 检查当前窗口是否满足条件
            if (i >= k - 1 && freq.size() == k) {
                maxSum = max(maxSum, currentSum);
            }
        }
        
        return maxSum;
    }
};

class Solution:
    def maximumSubarraySum(self, nums: List[int], k: int) -> int:
        n = len(nums)
        freq = {}
        current_sum = 0
        max_sum = 0
        
        for i in range(n):
            # 添加当前元素到窗口
            freq[nums[i]] = freq.get(nums[i], 0) + 1
            current_sum += nums[i]
            
            # 如果窗口大小超过k，移除左端元素
            if i >= k:
                left_element = nums[i - k]
                freq[left_element] -= 1
                if freq[left_element] == 0:
                    del freq[left_element]
                current_sum -= left_element
            
            # 检查当前窗口是否满足条件
            if i >= k - 1 and len(freq) == k:
                max_sum = max(max_sum, current_sum)
        
        return max_sum

public class Solution {
    public long MaximumSubarraySum(int[] nums, int k) {
        int n = nums.Length;
        var freq = new Dictionary<int, int>();
        long currentSum = 0;
        long maxSum = 0;
        
        for (int i = 0; i < n; i++) {
            // 添加当前元素到窗口
            if (freq.ContainsKey(nums[i])) {
                freq[nums[i]]++;
            } else {
                freq[nums[i]] = 1;
            }
            currentSum += nums[i];
            
            // 如果窗口大小超过k，移除左端元素
            if (i >= k) {
                int leftElement = nums[i - k];
                freq[leftElement]--;
                if (freq[leftElement] == 0) {
                    freq.Remove(leftElement);
                }
                currentSum -= leftElement;
            }
            
            // 检查当前窗口是否满足条件
            if (i >= k - 1 && freq.Count == k) {
                maxSum = Math.Max(maxSum, currentSum);
            }
        }
        
        return maxSum;
    }
}

var maximumSubarraySum = function(nums, k) {
    let maxSum = 0;
    let currentSum = 0;
    let freq = new Map();
    let left = 0;
    
    for (let right = 0; right < nums.length; right++) {
        currentSum += nums[right];
        freq.set(nums[right], (freq.get(nums[right]) || 0) + 1);
        
        if (right - left + 1 > k) {
            currentSum -= nums[left];
            freq.set(nums[left], freq.get(nums[left]) - 1);
            if (freq.get(nums[left]) === 0) {
                freq.delete(nums[left]);
            }
            left++;
        }
        
        if (right - left + 1 === k && freq.size === k) {
            maxSum = Math.max(maxSum, currentSum);
        }
    }
    
    return maxSum;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(n) - 每个元素最多被访问两次，哈希表操作为 O(1)
空间复杂度O(k) - 哈希表最多存储 k 个不同元素

相关题目