Medium

题目描述

给你一个整数数组 nums 和两个正整数 m 和 k。

返回 nums 中所有长度为 k 的几乎唯一子数组的最大和。如果不存在这样的子数组，返回 0。

如果 nums 的一个子数组包含至少 m 个不同元素，那么这个子数组就是几乎唯一的。

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

示例 1：

输入：nums = [2,6,7,3,1,7], m = 3, k = 4
输出：18
解释：有 3 个长度为 k = 4 的几乎唯一子数组。这些子数组是 [2, 6, 7, 3]、[6, 7, 3, 1] 和 [7, 3, 1, 7]。在这些子数组中，和最大的是 [2, 6, 7, 3]，和为 18。

示例 2：

输入：nums = [5,9,9,2,4,5,4], m = 1, k = 3
输出：23
解释：有 5 个长度为 k 的几乎唯一子数组。这些子数组是 [5, 9, 9]、[9, 9, 2]、[9, 2, 4]、[2, 4, 5] 和 [4, 5, 4]。在这些子数组中，和最大的是 [5, 9, 9]，和为 23。

示例 3：

输入：nums = [1,2,1,2,1,2,1], m = 3, k = 3
输出：0
解释：在给定的数组 [1,2,1,2,1,2,1] 中，不存在包含至少 m = 3 个不同元素的长度为 k = 3 的子数组。因此，不存在几乎唯一子数组，最大和为 0。

提示：

  • 1 <= nums.length <= 2 * 10^4
  • 1 <= m <= k <= nums.length
  • 1 <= nums[i] <= 10^9

解题思路

这道题需要找到所有长度为 k 且包含至少 m 个不同元素的子数组中和最大的那个。

解题思路：

我们可以使用滑动窗口技术来高效解决这个问题：

  1. 滑动窗口维护：维护一个长度为 k 的滑动窗口，使用哈希表记录窗口内每个元素的出现次数
  2. 不同元素统计：通过哈希表的大小来判断窗口内不同元素的个数
  3. 窗口移动：当窗口长度达到 k 时，检查是否满足至少 m 个不同元素的条件，如果满足则更新最大和
  4. 动态调整：每次移动窗口时，移除左边元素并添加右边元素，同时更新哈希表和当前和

算法步骤：

  • 初始化滑动窗口的左右边界、当前和以及哈希表
  • 扩展右边界直到窗口长度为 k
  • 当窗口长度等于 k 时，检查不同元素个数是否 ≥ m，更新最大和
  • 移动窗口：移除左边元素，添加新的右边元素
  • 重复直到遍历完所有可能的长度为 k 的子数组

这种方法的时间复杂度为 O(n)，空间复杂度为 O(k)，是最优解法。

代码实现

class Solution {
public:
    long long maxSum(vector<int>& nums, int m, int k) {
        int n = nums.size();
        if (n < k) return 0;
        
        unordered_map<int, int> count;
        long long currentSum = 0;
        long long maxSum = 0;
        
        // 构建初始窗口
        for (int i = 0; i < k; i++) {
            count[nums[i]]++;
            currentSum += nums[i];
        }
        
        // 检查初始窗口
        if (count.size() >= m) {
            maxSum = currentSum;
        }
        
        // 滑动窗口
        for (int i = k; i < n; i++) {
            // 移除左边元素
            int left = nums[i - k];
            count[left]--;
            if (count[left] == 0) {
                count.erase(left);
            }
            currentSum -= left;
            
            // 添加右边元素
            int right = nums[i];
            count[right]++;
            currentSum += right;
            
            // 检查当前窗口
            if (count.size() >= m) {
                maxSum = max(maxSum, currentSum);
            }
        }
        
        return maxSum;
    }
};

class Solution:
    def maxSum(self, nums: List[int], m: int, k: int) -> int:
        n = len(nums)
        if n < k:
            return 0
        
        count = {}
        current_sum = 0
        max_sum = 0
        
        # 构建初始窗口
        for i in range(k):
            count[nums[i]] = count.get(nums[i], 0) + 1
            current_sum += nums[i]
        
        # 检查初始窗口
        if len(count) >= m:
            max_sum = current_sum
        
        # 滑动窗口
        for i in range(k, n):
            # 移除左边元素
            left = nums[i - k]
            count[left] -= 1
            if count[left] == 0:
                del count[left]
            current_sum -= left
            
            # 添加右边元素
            right = nums[i]
            count[right] = count.get(right, 0) + 1
            current_sum += right
            
            # 检查当前窗口
            if len(count) >= m:
                max_sum = max(max_sum, current_sum)
        
        return max_sum

public class Solution {
    public long MaxSum(IList<int> nums, int m, int k) {
        int n = nums.Count;
        if (n < k) return 0;
        
        Dictionary<int, int> count = new Dictionary<int, int>();
        long currentSum = 0;
        long maxSum = 0;
        
        // 构建初始窗口
        for (int i = 0; i < k; i++) {
            if (count.ContainsKey(nums[i])) {
                count[nums[i]]++;
            } else {
                count[nums[i]] = 1;
            }
            currentSum += nums[i];
        }
        
        // 检查初始窗口
        if (count.Count >= m) {
            maxSum = currentSum;
        }
        
        // 滑动窗口
        for (int i = k; i < n; i++) {
            // 移除左边元素
            int left = nums[i - k];
            count[left]--;
            if (count[left] == 0) {
                count.Remove(left);
            }
            currentSum -= left;
            
            // 添加右边元素
            int right = nums[i];
            if (count.ContainsKey(right)) {
                count[right]++;
            } else {
                count[right] = 1;
            }
            currentSum += right;
            
            // 检查当前窗口
            if (count.Count >= m) {
                maxSum = Math.Max(maxSum, currentSum);
            }
        }
        
        return maxSum;
    }
}

var maxSum = function(nums, m, k) {
    if (nums.length < k) return 0;
    
    let maxSum = 0;
    let currentSum = 0;
    let freq = new Map();
    
    // Initialize first window
    for (let i = 0; i < k; i++) {
        currentSum += nums[i];
        freq.set(nums[i], (freq.get(nums[i]) || 0) + 1);
    }
    
    // Check if first window is almost unique
    if (freq.size >= m) {
        maxSum = currentSum;
    }
    
    // Slide the window
    for (let i = k; i < nums.length; i++) {
        // Remove leftmost element
        let leftElement = nums[i - k];
        currentSum -= leftElement;
        freq.set(leftElement, freq.get(leftElement) - 1);
        if (freq.get(leftElement) === 0) {
            freq.delete(leftElement);
        }
        
        // Add rightmost element
        let rightElement = nums[i];
        currentSum += rightElement;
        freq.set(rightElement, (freq.get(rightElement) || 0) + 1);
        
        // Check if current window is almost unique
        if (freq.size >= m) {
            maxSum = Math.max(maxSum, currentSum);
        }
    }
    
    return maxSum;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值说明
时间复杂度O(n)需要遍历数组一次，每次操作哈希表的时间为O(1)
空间复杂度O(k)哈希表最多存储k个不同元素