- 3.1 算法解释
- 3.2 两数之和 II
- 题解
- 3.3 合并两个有序数组
- 88. 合并两个有序数组Easy">88. 合并两个有序数组Easy
- 题解
- 3.4 环形链表
- 142. 环形链表 IIMid">142. 环形链表 IIMid
- 题解
- 🐸3.5 最小覆盖子串(滑动窗口)
- 76. 最小覆盖子串Hard">76. 最小覆盖子串Hard
- 🐸3.6 无重复字符的最长子串（滑动窗口）
- 3. 无重复字符的最长子串Mid">3. 无重复字符的最长子串Mid
- 3.7 盛最多水的容器
- 11. 盛最多水的容器Mid">11. 盛最多水的容器Mid
- 3.8 三数之和
- 3.9 颜色分类
- 🐸3.10 子数组最大平均数 I（滑动窗口）
- 643. 子数组最大平均数 IEasy">643. 子数组最大平均数 IEasy
- 🐸3.11 长度最小的子数组（滑动窗口）
- 209. 长度最小的子数组Mid">209. 长度最小的子数组Mid
- 🐸3.12 删除子数组的最大得分（滑动窗口）
- 1695. 删除子数组的最大得分Mid">1695. 删除子数组的最大得分Mid
- 🐸3.13 找到字符串中所有字母异位词（滑动窗口）
- 🐸3.14 字符串的排列（滑动窗口）
- 567. 字符串的排列Mid">567. 字符串的排列Mid
- 🐸3.15 最大连续1的个数 III（滑动窗口）
- 🐸3.16 尽可能使字符串相等（滑动窗口）
- 1208. 尽可能使字符串相等Mid">1208. 尽可能使字符串相等Mid
- 🚩3.17 爱生气的书店老板（滑动窗口，窗口大小固定）
- 1052. 爱生气的书店老板Mid">1052. 爱生气的书店老板Mid
- 🚩3.18 可获得的最大点数（滑动窗口，窗口大小固定）
- 1423. 可获得的最大点数Mid">1423. 可获得的最大点数Mid
- 1423. 可获得的最大点数Mid">1423. 可获得的最大点数Mid
3.1 算法解释
双指针主要用于遍历数组，两个指针指向不同的元素，从而协同完成任务。也可以延伸到多 个数组的多个指针。
若两个指针指向同一数组，遍历方向相同且不会相交，则也称为滑动窗口（两个指针包围的 区域即为当前的窗口），经常用于区间搜索。
若两个指针指向同一数组，但是遍历方向相反，则可以用来进行搜索，待搜索的数组往往是
排好序的。
3.2 两数之和 II
167. 两数之和 II - 输入有序数组Mid
给你一个下标从 1 开始的整数数组 numbers ，该数组已按 非递减顺序排列 ，请你从数组中找出满足相加之和等于目标数 target 的两个数。如果设这两个数分别是 numbers[index1] 和 numbers[index2] ，则 1 <= index1 < index2 <= numbers.length 。
以长度为 2 的整数数组 [index1, index2] 的形式返回这两个整数的下标 index1 和 _index2。
你可以假设每个输入 只对应唯一的答案 ，而且你 不可以 重复使用相同的元素。
你所设计的解决方案必须只使用常量级的额外空间。
示例 1：
输入：numbers = [**_2,7,11,15], target = 9 输出：[1,2] 解释：2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。返回 [1, 2] 。
示例 2：
输入：numbers = [2,3,4], target = 6 输出：[1,3] 解释：2 与 4 之和等于目标数 6 。因此 index1 = 1, index2 = 3 。返回 [1, 3] 。
示例 3：
输入：numbers = [-1,0], target = -1 输出：[1,2] 解释：**-1 与 0 之和等于目标数 -1 。因此 index1 = 1, index2 = 2 。返回 [1, 2] 。
题解
因为数组已经排好序，我们可以采用方向相反的双指针来寻找这两个数字，一个初始指向最 小的元素，即数组最左边，向右遍历；一个初始指向最大的元素，即数组最右边，向左遍历。 如果两个指针指向元素的和等于给定值，那么它们就是我们要的结果。
如果两个指针指向元 素的和小于给定值，我们把左边的指针右移一位，使得当前的和增加一点。如果两个指针指向元 素的和大于给定值，我们把右边的指针左移一位，使得当前的和减少一点。
class Solution {public:vector<int> twoSum(vector<int>& numbers, int target) {int l = 0, r = numbers.size() - 1;while (l < r) {int sum = numbers[l] + numbers[r];if (sum == target)return {l + 1, r + 1};else if (sum < target)l++;elser--;}return {};}};
3.3 合并两个有序数组
88. 合并两个有序数组Easy
给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。
请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。
注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。
示例 1：
输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3 输出：[1,2,2,3,5,6] 解释：需要合并 [1,2,3] 和 [2,5,6] 。 合并结果是 [1,2,2,3,5,6] ，其中斜体加粗标注的为 nums1 中的元素。
示例 2：
输入：nums1 = [1], m = 1, nums2 = [], n = 0 输出：[1] 解释：需要合并 [1] 和 [] 。 合并结果是 [1] 。
示例 3：
输入：nums1 = [0], m = 0, nums2 = [1], n = 1 输出：[1] 解释：需要合并的数组是 [] 和 [1] 。 合并结果是 [1] 。 注意，因为 m = 0 ，所以 nums1 中没有元素。nums1 中仅存的 0 仅仅是为了确保合并结果可以顺利存放到 nums1 中。
题解
因为这两个数组已经排好序，我们可以把两个指针分别放在两个数组的末尾，即 nums1 的
m − 1 位和 nums2 的 n − 1 位。不断比较大小，并将较大的放在nums1的最后（起始位置为 m + n - 1）。
class Solution {
public:
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
int p1 = m - 1, p2 = n - 1, p3 = m + n - 1;
while (p1 >= 0 && p2 >= 0) {
nums1[p3--] = nums1[p1] > nums2[p2]? nums1[p1--] : nums2[p2--];
}
while (p2 >= 0) {
nums1[p3--] = nums2[p2--];
}
}
};
3.4 环形链表
142. 环形链表 IIMid
给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
不允许修改 链表。
示例 1：
输入：head = [3,2,0,-4], pos = 1 输出：返回索引为 1 的链表节点 解释：链表中有一个环，其尾部连接到第二个节点。
示例 2：
输入：head = [1,2], pos = 0 输出：返回索引为 0 的链表节点 解释：链表中有一个环，其尾部连接到第一个节点。
示例 3：
输入：head = [1], pos = -1 输出：返回 null 解释：链表中没有环。
题解
对于链表找环路的问题，有一个通用的解法——快慢指针（Floyd 判圈法）。给定两个指针，分别命名为 slow 和 fast，起始位置在链表的开头。每次 fast 前进两步，slow 前进一步。如果 fast 可以走到尽头，那么说明没有环路；如果 fast 可以无限走下去，那么说明一定有环路，且一定存在一个时刻 slow和 fast 相遇。当 slow和 fast 第一次相遇时，我们将 fast 重新移动到链表开头，并让 slow和 fast 每次都前进一步。当 slow和 fast 第二次相遇时，相遇的节点即为环路的开始点。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
ListNode* slow = head;
ListNode* fast = head;
//判断是否存在回路
do {
if (!fast || !fast->next)
return nullptr;
fast = fast->next->next;
slow = slow->next;
} while (fast != slow);
//如果存在，查找环路节点
fast = head;
while (fast != slow) {
slow = slow->next;
fast = fast->next;
}
return fast;
}
};
🐸3.5 最小覆盖子串(滑动窗口)
76. 最小覆盖子串Hard
给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 “” 。
注意：
- 对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
- 如果 s 中存在这样的子串，我们保证它是唯一的答案。
示例 1：
输入：s = “ADOBECODEBANC”, t = “ABC” 输出：“BANC”
示例 2：
输入：s = “a”, t = “a” 输出：“a”
示例 3:
输入: s = “a”, t = “aa” 输出: “” 解释: t 中两个字符 ‘a’ 均应包含在 s 的子串中， 因此没有符合条件的子字符串，返回空字符串。
class Solution {
public:
string minWindow(string s, string t) {
//key:字符，value:出现的次数
//need记录t的信息，windows记录滑动窗口的信息
unordered_map<char, int> need, windows;
for (char c : t) {
need[c]++;
}
int l = 0, r = 0, cnt = 0;
int start = 0, len = s.length() + 1;
while (r < s.length()) {
char c = s[r];
r++;
if (need.count(c) == 1) {
windows[c]++;
if (windows[c] == need[c]) {
cnt++;
}
}
//cnt == need.size()条件成立说明已经找到
//符合条件的字串，但是题目要求最短，所以收
//缩窗口继续寻找
while (cnt == need.size()) {
if (r - l < len) {
start = l;
len = r - l;
}
char d = s[l];
l++;
if (need.count(d) == 1) {
if (windows[d] == need[d]) {
cnt--;
}
windows[d]--;
}
}
}
return len == s.length() + 1 ? "" : s.substr(start, len);
}
};
🐸3.6 无重复字符的最长子串（滑动窗口）
3. 无重复字符的最长子串Mid
给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: s = “abcabcbb” 输出: 3 解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。
示例 2:
输入: s = “bbbbb” 输出: 1 解释: 因为无重复字符的最长子串是 “b”，所以其长度为 1。
示例 3:
输入: s = “pwwkew” 输出: 3 解释: 因为无重复字符的最长子串是 “wke”，所以其长度为 3。 请注意，你的答案必须是 子串 的长度，”pwke” 是一个子序列，不是子串。
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int l, r = 0;
int res = 0;
unordered_map<char, int> windows;
while (r < s.length()) {
char c = s[r];
r++;
windows[c]++;
while (windows[c] > 1) {
char d = s[l];
l++;
windows[d]--;
}
res = max(res, r - l);
}
return res;
}
};
3.7 盛最多水的容器
11. 盛最多水的容器Mid
给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。
找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
返回容器可以储存的最大水量。
说明：你不能倾斜容器。
示例 1：
输入：[1,8,6,2,5,4,8,3,7] 输出：49 解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。
示例 2：
输入：height = [1,1] 输出：1
class Solution {
public:
int maxArea(vector<int>& height) {
int l = 0, r = height.size() - 1;
int res = 0;
while (l < r) {
res = max(res, (r - l) * min(height[l], height[r]));
if (height[l] >= height[r]) r--;
else l++;
}
return res;
}
};
3.8 三数之和
15. 三数之和Mid
给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 _a + b + c = _0 ？请你找出所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。
示例 1：
输入：nums = [-1,0,1,2,-1,-4] 输出：[[-1,-1,2],[-1,0,1]]
示例 2：
输入：nums = [] 输出：[]
示例 3：
输入：nums = [0] 输出：[]
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
int size = nums.size();
// 特判
if (size < 3)
return {};
vector<vector<int>> res;// 结果集
sort(nums.begin(), nums.end());// 排序解决重复问题，默认升序
for (int i = 0; i < size; i++)
{
// 特判，如果第一个数组已经大于0，递增序列相加不可能为0
if (nums[i] > 0)
return res;
// 去重
if (i > 0 && nums[i] == nums[i-1])
continue;
int left = i + 1;
int right = size - 1;
while (left < right)
{
if (nums[left] + nums[right] + nums[i] > 0)
right--;// 三数之和太大，移动右指针
else if (nums[left] + nums[right] + nums[i] < 0)
left++;// 三数之和太小，移动左指针
else
{
vector<int> temp = {nums[i], nums[left], nums[right]};
res.push_back(temp);
left++;
right--;
// 去重，左右指针移动过程中同样需要去重
while (left < right && nums[left] == nums[left - 1])
left++;
while (left < right && nums[right] == nums[right + 1])
right--;
}
}
}
return res;
}
};
3.9 颜色分类
75. 颜色分类Mid
给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
必须在不使用库的sort函数的情况下解决这个问题。
示例 1：
输入：nums = [2,0,2,1,1,0] 输出：[0,0,1,1,2,2]
示例 2：
输入：nums = [2,0,1] 输出：[0,1,2]
class Solution {
public:
void sortColors(vector<int>& nums) {
int cur = 0;
int p0 = 0, p1 = 0;
for (int cur = 0; cur < nums.size(); ++cur) {
if (nums[cur] == 0) {
swap(nums[cur], nums[p0]);
if (p0 < p1) {
// 可能把1交换出去了
swap(nums[cur], nums[p1]);
}
p0++;
p1++;
}
else if (nums[cur] == 1) {
swap(nums[cur], nums[p1]);
p1++;
}
}
}
void swap(int& a, int& b) {
int tmp = a;
a = b;
b = tmp;
}
};
🐸3.10 子数组最大平均数 I（滑动窗口）
643. 子数组最大平均数 IEasy
给你一个由 n 个元素组成的整数数组 nums 和一个整数 k 。
请你找出平均数最大且 长度为 k 的连续子数组，并输出该最大平均数。
任何误差小于 10-5 的答案都将被视为正确答案。
示例 1：
输入：nums = [1,12,-5,-6,50,3], k = 4 输出：12.75 解释：最大平均数 (12-5-6+50)/4 = 51/4 = 12.75
示例 2：
输入：nums = [5], k = 1 输出：5.00000
class Solution {
public:
double findMaxAverage(vector<int>& nums, int k) {
int l = 0, r = 0;
double Max = INT_MIN;
double sum = 0;
while (r < nums.size()) {
int c = nums[r];
sum += c;
r++;
if (r - l == k) {
Max = max(Max, sum / k);
int d = nums[l];
sum -= d;
l++;
}
}
return Max;
}
};
🐸3.11 长度最小的子数组（滑动窗口）
209. 长度最小的子数组Mid
给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, …, numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。
示例 1：
输入：target = 7, nums = [2,3,1,2,4,3] 输出：2 解释：子数组 [4,3] 是该条件下的长度最小的子数组。
示例 2：
输入：target = 4, nums = [1,4,4] 输出：1
示例 3：
输入：target = 11, nums = [1,1,1,1,1,1,1,1] 输出：0
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
int l = 0, r = 0;
int len = INT_MAX;
int sum = 0;
while (r < nums.size()) {
int c = nums[r];
r++;
sum += c;
while (sum >= target) {
int d = nums[l];
l++;
sum -= d;
len = min(len, r - l + 1);
}
}
return len == INT_MAX ? 0 : len;
}
};
🐸3.12 删除子数组的最大得分（滑动窗口）
1695. 删除子数组的最大得分Mid
给你一个正整数数组 nums ，请你从中删除一个含有 若干不同元素 的子数组。删除子数组的 得分 就是子数组各元素之 和 。
返回 只删除一个 子数组可获得的 最大得分 。
如果数组 b 是数组 a 的一个连续子序列，即如果它等于 a[l],a[l+1],…,a[r] ，那么它就是 a 的一个子数组。
示例 1：
输入：nums = [4,2,4,5,6] 输出：17 解释：最优子数组是 [2,4,5,6]
示例 2：
输入：nums = [5,2,1,2,5,2,1,2,5] 输出：8 解释：最优子数组是 [5,2,1] 或 [1,2,5]
class Solution {
public:
int maximumUniqueSubarray(vector<int>& nums) {
int l = 0, r = 0;
int max_score = 0;
int sum = 0;
unordered_map<int, int> windows;
while (r < nums.size()) {
int c = nums[r];
r++;
windows[c]++;
sum += c;
while (windows[c] > 1) {
int d = nums[l];
l++;
windows[d]--;
sum -= d;
}
max_score = max(max_score, sum);
}
return max_score;
}
};
🐸3.13 找到字符串中所有字母异位词（滑动窗口）
438. 找到字符串中所有字母异位词Mid
给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。
示例 1:
输入: s = “cbaebabacd”, p = “abc” 输出: [0,6] 解释: 起始索引等于 0 的子串是 “cba”, 它是 “abc” 的异位词。 起始索引等于 6 的子串是 “bac”, 它是 “abc” 的异位词。
示例 2:
输入: s = “abab”, p = “ab” 输出: [0,1,2] 解释: 起始索引等于 0 的子串是 “ab”, 它是 “ab” 的异位词。 起始索引等于 1 的子串是 “ba”, 它是 “ab” 的异位词。 起始索引等于 2 的子串是 “ab”, 它是 “ab” 的异位词。
class Solution {
public:
vector<int> findAnagrams(string s, string p) {
vector<int> res;
unordered_map<char, int> need;
unordered_map<char, int> windows;
for (char c : p) {
need[c]++;
}
int l = 0, r = 0, cnt = 0;
while (r < s.length()) {
char c = s[r];
r++;
if (need.count(c) == 1) {
windows[c]++;
if (need[c] == windows[c]) {
cnt++;
}
}
while (r - l >= p.length()) {
if (cnt == need.size())
res.push_back(l);
char d = s[l];
l++;
if (need.count(d) == 1) {
if (need[d] == windows[d]) {
cnt--;
}
windows[d]--;
}
}
}
return res;
}
};
🐸3.14 字符串的排列（滑动窗口）
567. 字符串的排列Mid
给你两个字符串 s1 和 s2 ，写一个函数来判断 s2 是否包含 s1 的排列。如果是，返回 true ；否则，返回 false 。
换句话说，s1 的排列之一是 s2 的 子串 。
示例 1：
输入：s1 = “ab” s2 = “eidbaooo” 输出：true 解释：s2 包含 s1 的排列之一 (“ba”).
示例 2：
输入：s1= “ab” s2 = “eidboaoo” 输出：false
class Solution {
public:
bool checkInclusion(string s1, string s2) {
unordered_map<char, int> need;
unordered_map<char, int> windows;
int l = 0, r = 0, cnt = 0;
for (char c: s1) {
need[c]++;
}
while (r < s2.length()) {
char c = s2[r];
r++;
if (need.count(c) == 1) {
windows[c]++;
if (windows[c] == need[c]) {
cnt++;
}
}
while (r - l >= s1.length()) {
if (cnt == need.size()) {
return true;
}
char d = s2[l];
l++;
if (need.count(d) == 1) {
if (windows[d] == need[d]) {
cnt--;
}
windows[d]--;
}
}
}
return false;
}
};
🐸3.15 最大连续1的个数 III（滑动窗口）
1004. 最大连续1的个数 IIIMid
给定一个二进制数组 nums 和一个整数 k，如果可以翻转最多 k 个 0 ，则返回 数组中连续 1 的最大个数 。
示例 1：
输入：nums = [1,1,1,0,0,0,1,1,1,1,0], K = 2 输出：6 解释：[1,1,1,0,0,1,1,1,1,1,1] 粗体数字从 0 翻转到 1，最长的子数组长度为 6。
示例 2：
输入：nums = [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], K = 3 输出：10 解释：[0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,1,1,1,1] 粗体数字从 0 翻转到 1，最长的子数组长度为 10。
class Solution {
public:
int longestOnes(vector<int>& nums, int k) {
int l = 0, r = 0, cnt = 0;
int res = INT_MIN;
while (r < nums.size()) {
int c = nums[r];
r++;
if (c == 0) {
cnt++;
}
if (cnt > k) {
while (nums[l] == 1) {
l++;
}
cnt--;
l++;
}
res = max(res, r - l);
}
return res;
}
};
🐸3.16 尽可能使字符串相等（滑动窗口）
1208. 尽可能使字符串相等Mid
给你两个长度相同的字符串，s 和 t。
将 s 中的第 i 个字符变到 t 中的第 i 个字符需要 |s[i] - t[i]| 的开销（开销可能为 0），也就是两个字符的 ASCII 码值的差的绝对值。
用于变更字符串的最大预算是 maxCost。在转化字符串时，总开销应当小于等于该预算，这也意味着字符串的转化可能是不完全的。
如果你可以将 s 的子字符串转化为它在 t 中对应的子字符串，则返回可以转化的最大长度。
如果 s 中没有子字符串可以转化成 t 中对应的子字符串，则返回 0。
示例 1：
输入：s = “abcd”, t = “bcdf”, maxCost = 3 输出：3 解释：s 中的 “abc” 可以变为 “bcd”。开销为 3，所以最大长度为 3。
示例 2：
输入：s = “abcd”, t = “cdef”, maxCost = 3 输出：1 解释：s 中的任一字符要想变成 t 中对应的字符，其开销都是 2。因此，最大长度为 1。
示例 3：
输入：s = “abcd”, t = “acde”, maxCost = 0 输出：1 解释：a -> a, cost = 0，字符串未发生变化，所以最大长度为 1。
class Solution {
public:
int equalSubstring(string s, string t, int maxCost) {
int l = 0, r = 0, cnt = 0;
int res = INT_MIN;
while (r < s.length()) {
char c1 = s[r];
char c2 = t[r];
r++;
cnt += abs(c2 - c1);
while (cnt > maxCost) {
char d1 = s[l];
char d2 = t[l];
l++;
cnt -= abs(d2 - d1);
}
res = max(res, r - l);
}
return res;
}
};
🚩3.17 爱生气的书店老板（滑动窗口，窗口大小固定）
1052. 爱生气的书店老板Mid
有一个书店老板，他的书店开了 n 分钟。每分钟都有一些顾客进入这家商店。给定一个长度为 n 的整数数组 customers ，其中 customers[i] 是在第 i 分钟开始时进入商店的顾客的编号顾客的数量，所有这些顾客在第 i 分钟结束后离开。
在某些时候，书店老板会生气。 如果书店老板在第 i 分钟生气，那么 grumpy[i] = 1，否则 grumpy[i] = 0。
当书店老板生气时，那一分钟的顾客就会不满意，若老板不生气则顾客是满意的。
书店老板知道一个秘密技巧，能抑制自己的情绪，可以让自己连续 minutes 分钟不生气，但却只能使用一次。
请你返回 这一天营业下来，最多有多少客户能够感到满意 。
示例 1：
输入：customers = [1,0,1,2,1,1,7,5], grumpy = [0,1,0,1,0,1,0,1], minutes = 3 输出：16 解释：书店老板在最后 3 分钟保持冷静。 感到满意的最大客户数量 = 1 + 1 + 1 + 1 + 7 + 5 = 16.
示例 2：
输入：customers = [1], grumpy = [0], minutes = 1 输出：1
class Solution {
public:
int maxSatisfied(vector<int>& customers, vector<int>& grumpy, int minutes) {
int ans = 0;
for (int i = 0; i < customers.size(); i++) {
if (grumpy[i] == 0) {
ans += customers[i];
}
}
int l = 0, r = minutes;
int sum = 0;
for (int i = 0; i < r; i++) {
if (grumpy[i] == 1) {
sum += customers[i];
}
}
int res = sum;
while (r < customers.size()) {
if (grumpy[l] == 1) {
sum -= customers[l];
}
l++;
if (grumpy[r] == 1) {
sum += customers[r];
}
r++;
res = max(res, sum);
}
return (res + ans);
}
};
🚩3.18 可获得的最大点数（滑动窗口，窗口大小固定）
1423. 可获得的最大点数Mid
几张卡牌 排成一行，每张卡牌都有一个对应的点数。点数由整数数组 cardPoints 给出。
每次行动，你可以从行的开头或者末尾拿一张卡牌，最终你必须正好拿 k 张卡牌。
你的点数就是你拿到手中的所有卡牌的点数之和。
给你一个整数数组 cardPoints 和整数 k，请你返回可以获得的最大点数。
示例 1：
输入：cardPoints = [1,2,3,4,5,6,1], k = 3 输出：12 解释：第一次行动，不管拿哪张牌，你的点数总是 1 。但是，先拿最右边的卡牌将会最大化你的可获得点数。最优策略是拿右边的三张牌，最终点数为 1 + 6 + 5 = 12 。
示例 2：
输入：cardPoints = [2,2,2], k = 2 输出：4 解释：无论你拿起哪两张卡牌，可获得的点数总是 4 。
示例 3：
输入：cardPoints = [9,7,7,9,7,7,9], k = 7 输出：55 解释：你必须拿起所有卡牌，可以获得的点数为所有卡牌的点数之和。
示例 4：
输入：cardPoints = [1,1000,1], k = 1 输出：1 解释：你无法拿到中间那张卡牌，所以可以获得的最大点数为 1 。
示例 5：
输入：cardPoints = [1,79,80,1,1,1,200,1], k = 3 输出：202
class Solution {
public:
int maxScore(vector<int>& cardPoints, int k) {
int l = 0, r = cardPoints.size() - k;
int sum = 0;
for (int i = 0; i < r; i++) {
sum += cardPoints[i];
}
int res = sum;
while (r < cardPoints.size()) {
int c = cardPoints[r];
r++;
int d = cardPoints[l];
l++;
sum = sum + c - d;
res = min(res, sum);
}
return accumulate(cardPoints.begin(), cardPoints.end(), 0) - res;
}
};
若有收获，就点个赞吧
0 人点赞
