2841-几乎唯一子数组的最大和

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:25 2023-09-13 16:06:25 Updated    

给你一个整数数组 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 = 3 的几乎唯一子数组。分别为 [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
**解释：** 输入数组中不存在长度为 k = 3 的子数组含有至少  m = 3 个互不相同元素的子数组。所以不存在几乎唯一子数组，最大和为 0 。

提示：

  • 1 <= nums.length <= 2 * 104
  • 1 <= m <= k <= nums.length
  • 1 <= nums[i] <= 109

请看 视频讲解 第三题。

看到「长度固定的子数组」就要想到滑动窗口！

维护窗口内的元素出现次数 cnt，以及元素和 sum。

[sol-Python3]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def maxSum(self, nums: List[int], m: int, k: int) -> int:
        ans = 0
        s = sum(nums[:k - 1])  # 先统计 k-1 个数
        cnt = Counter(nums[:k - 1])
        for out, in_ in zip(nums, nums[k - 1:]):
            s += in_  # 再添加一个数就是 k 个数了
            cnt[in_] += 1
            if len(cnt) >= m:
                ans = max(ans, s)
                
            s -= out  # 下一个子数组不包含 out，移出窗口
            cnt[out] -= 1
            if cnt[out] == 0:
                del cnt[out]
        return ans
[sol-Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public long maxSum(List<Integer> nums, int m, int k) {
        var a = nums.stream().mapToInt(i -> i).toArray();
        long ans = 0, sum = 0;
        var cnt = new HashMap<Integer, Integer>();
        for (int i = 0; i < k - 1; i++) { // 先统计 k-1 个数
            sum += a[i];
            cnt.merge(a[i], 1, Integer::sum); // cnt[a[i]]++
        }
        for (int i = k - 1; i < nums.size(); i++) {
            sum += a[i]; // 再添加一个数就是 k 个数了
            cnt.merge(a[i], 1, Integer::sum); // cnt[a[i]]++
            if (cnt.size() >= m)
                ans = Math.max(ans, sum);

            int out = a[i - k + 1];
            sum -= out; // 下一个子数组不包含 out，移出窗口
            if (cnt.merge(out, -1, Integer::sum) == 0) // --cnt[out] == 0
                cnt.remove(out);
        }
        return ans;
    }
}
[sol-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    long long maxSum(vector<int> &nums, int m, int k) {
        long long ans = 0, sum = 0;
        unordered_map<int, int> cnt;
        for (int i = 0; i < k - 1; i++) { // 先统计 k-1 个数
            sum += nums[i];
            cnt[nums[i]]++;
        }
        for (int i = k - 1; i < nums.size(); i++) {
            sum += nums[i]; // 再添加一个数就是 k 个数了
            cnt[nums[i]]++;
            if (cnt.size() >= m)
                ans = max(ans, sum);

            int out = nums[i - k + 1];
            sum -= out; // 下一个子数组不包含 out，移出窗口
            if (--cnt[out] == 0)
                cnt.erase(out);
        }
        return ans;
    }
};
[sol-Go]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
func maxSum(nums []int, m, k int) (ans int64) {
	sum := int64(0)
	cnt := map[int]int{}
	for _, x := range nums[:k-1] { // 先统计 k-1 个数
		sum += int64(x)
		cnt[x]++
	}
	for i, in := range nums[k-1:] {
		sum += int64(in) // 再添加一个数就是 k 个数了
		cnt[in]++
		if len(cnt) >= m && sum > ans {
			ans = sum
		}

		out := nums[i]
		sum -= int64(out) // 下一个子数组不包含 out，移出窗口
		cnt[out]--
		if cnt[out] == 0 {
			delete(cnt, out)
		}
	}
	return
}

复杂度分析

  • 时间复杂度：\mathcal{O}(n)，其中 n 为 nums 的长度。
  • 空间复杂度：\mathcal{O}(k)。哈希表的大小不会超过窗口长度，即 k。

练习：滑动窗口

 Comments
On this page
2841-几乎唯一子数组的最大和
  1. 练习：滑动窗口