一、2461. 长度为 K 子数组中的最大和
给你一个整数数组 nums 和一个整数 k 。请你从 nums 中满足下述条件的全部子数组中找出最大子数组和：
- 子数组的长度是
k，且 - 子数组中的所有元素 各不相同 。
返回满足题面要求的最大子数组和。如果不存在子数组满足这些条件，返回 0 。
子数组 是数组中一段连续非空的元素序列。
代码：
class Solution {
public:
long long maximumSubarraySum(vector<int>& nums, int k) {
long long sum = 0, ans = 0;
int l = 0;
unordered_map<int, int> hash;
// 初始化前 k-1 个元素
for (int r = 0; r < k - 1; ++r) {
sum += nums[r];
hash[nums[r]]++;
}
// 滑动窗口从第 k 个元素开始
for (int r = k - 1; r < nums.size(); ++r) {
sum += nums[r]; // 加入右端元素
hash[nums[r]]++; // 更新右端元素的计数
// 检查是否满足条件
if (hash.size() == k) {
ans = max(ans, sum);
}
// 移除左端元素
hash[nums[l]]--;
sum -= nums[l];
if (hash[nums[l]] == 0) {
hash.erase(nums[l]);
}
l++; // 滑动窗口的左端
}
return ans;
}
};更简洁版本：
一个for循环解决
class Solution {
public:
long long maximumSubarraySum(vector<int>& nums, int k) {
long long sum = 0, ans = 0;
unordered_map<int, int> hash;
for (int r = 0; r < nums.size(); ++r) {
sum += nums[r]; // 增加当前右端元素到窗口和
hash[nums[r]]++; // 更新右端元素的计数
// 当窗口大小达到 k，检查是否满足条件
if (r >= k - 1) {
if (hash.size() == k) {
ans = max(ans, sum);
}
// 滑动窗口，移除左端元素
if (--hash[nums[r - k + 1]] == 0) {
hash.erase(nums[r - k + 1]);
}
sum -= nums[r - k + 1]; // 从窗口和中减去左端元素
}
}
return ans;
}
};
思路：
1.先判断哈希表长度是否等于k（即元素各不相同），再维护最大和
2.在有限制条件时，最好先初始化到 k - 1
二、1423. 可获得的最大点数
题目：
几张卡牌 排成一行，每张卡牌都有一个对应的点数。点数由整数数组 cardPoints 给出。
每次行动，你可以从行的开头或者末尾拿一张卡牌，最终你必须正好拿 k 张卡牌。
你的点数就是你拿到手中的所有卡牌的点数之和。
给你一个整数数组 cardPoints 和整数 k，请你返回可以获得的最大点数。
代码：
class Solution {
public:
int maxScore(vector<int>& cardPoints, int k) {
long long totalSum = 0, windowSum = 0, maxScore = 0;
int n = cardPoints.size();
// 计算总和
for (int i = 0; i < n; ++i) {
totalSum += cardPoints[i];
}
// 初始窗口大小为n-k，计算窗口的和
for (int i = 0; i < n - k; ++i) {
windowSum += cardPoints[i];
}
// 滑动窗口：逐步将窗口移动，更新最大分数
maxScore = totalSum - windowSum; // 初始的最大分数是选取剩下的k张卡牌
for (int i = n - k; i < n; ++i) {
windowSum += cardPoints[i]; // 加入新的元素
windowSum -= cardPoints[i - (n - k)]; // 移除旧的元素
maxScore = max(maxScore, totalSum - windowSum); // 计算可能的最大分数
}
return maxScore;
}
};
思路：
1.将求两端的和转化为求总和减中间的差，这种差集思想很巧妙
2.还有方法二，因为题目说了k < .size 所以可以把后k个元素移到前面再计算滑动窗口和
三、1652. 拆炸弹
你有一个炸弹需要拆除，时间紧迫！你的情报员会给你一个长度为 n 的 循环 数组 code 以及一个密钥 k 。
为了获得正确的密码，你需要替换掉每一个数字。所有数字会 同时 被替换。
- 如果
k > 0，将第i个数字用 接下来k个数字之和替换。 - 如果
k < 0，将第i个数字用 之前k个数字之和替换。 - 如果
k == 0，将第i个数字用0替换。
由于 code 是循环的， code[n-1] 下一个元素是 code[0] ，且 code[0] 前一个元素是 code[n-1] 。
给你 循环 数组 code 和整数密钥 k ，请你返回解密后的结果来拆除炸弹！
代码：
#include <numeric> // 引入 accumulate
class Solution {
public:
vector<int> decrypt(vector<int>& code, int k) {
int len = code.size();
vector<int> newCode(len);
// 剪枝，如果 k == 0，则直接返回全是 0 的数组
if (k == 0) {
return newCode;
}
int right; // 右侧窗口边界
if (k > 0) {
// 对于 k > 0，窗口的右边界从 k+1 开始
right = k + 1;
} else {
// 对于 k < 0，窗口的右边界从 n 开始
right = len;
}
k = abs(k); // 取 k 的绝对值
// 初始化滑动窗口的和
int sum = accumulate(code.begin() + right - k, code.begin() + right, 0);
// 滑动窗口计算
for (int i = 0; i < len; i++) {
// 设置新数组的当前元素为当前窗口的和
newCode[i] = sum;
// 滑动窗口：更新 sum，增加新进入窗口的元素，减少离开窗口的元素
sum += code[right % len] - code[(right - k) % len];
// 右边界右移
right++;
}
return newCode;
}
};
思路：
1.梦回循环数组求长度，要取余，滑动窗口现在一直向右，右到尽头后继续取余继续右
2.在分别研究了k < 0 和 k > 0 的情况后发现滑动窗口都是向右滑动，只是初始位置不一样故可以将代码操作统一
新知识：
std::accumulate——计算区间内元素的和
std::accumulate(first, last, init);
first：累加的开始位置。last：累加的结束位置。init：初始值。