跳到主要内容

2461.长度为K子数组中的最大和

链接：2461.长度为K子数组中的最大和
难度：Medium
标签：数组、哈希表、滑动窗口
简介：返回满足题面要求的最大子数组和。如果不存在子数组满足这些条件，返回 0 。

题解 1 - cpp​

  • 编辑时间：2022-11-06
  • 执行用时：192ms
  • 内存消耗：90.8MB
  • 编程语言：cpp
  • 解法介绍：滑动窗口遍历。
class Solution {
public:
    long long maximumSubarraySum(vector<int>& nums, int k) {
        long long sum = 0, ans = 0;
        int l = 0, r = 0, n = nums.size();
        int cnt = 0;
        unordered_map<int, int> m;
        while (r < k) {
            m[nums[r]]++;
            sum += nums[r];
            if (m[nums[r]] == 2) cnt++;
            r++;
        }
        if (cnt == 0) ans = sum;
        // cout << "l = " << l << ", r = " << r << endl;
        // cout << "sum = " << sum << ", cnt = " << cnt << endl;
        while (r < n) {
            sum -= nums[l];
            m[nums[l]]--;
            if (m[nums[l]] == 1) cnt--;
            l++;
            sum += nums[r];
            m[nums[r]]++;
            if (m[nums[r]] == 2) cnt++;
            r++;
            // cout << "l = " << l << ", r = " << r << endl;
            if (cnt == 0) ans = max(ans, sum);
        }
        return ans;
    }
};