一、滑动窗口

写法：先构建一个初始窗口或直接从0开始构建，再移动，维护窗口内数据信息（和、个数....）

1.定长滑动窗口

知识点： 1.以窗口移动 2.前缀和配合计算窗口内数据和或维护一个sum值通过增删维护窗口内数据和 3.维护一组不重复数据，可以用set，也可以通过用map，维护map对应数据键值，0（不重复），1（唯一），大于1（重复）。 4.计数排序维护一个窗口内minmax不大的数组排序 5.stringAPI，与int互相转化API，

1_219.存在重复元素（简单）

给你一个整数数组 nums 和一个整数 k ，判断数组中是否存在两个 不同的索引 i 和 j ，满足 nums[i] == nums[j] 且 abs(i - j) <= k 。如果存在，返回 true ；否则，返回 false 。

思路：保持长为k窗口内无相同元素，指针i从0向右撑满为k后移动，若有窗口内有与窗口外指针i指向元素相同则满足。

2_594.最长和谐子列（简单）

和谐数组是指一个数组里元素的最大值和最小值之间的差别 正好是 1 。现在，给你一个整数数组 nums ，请你在所有可能的子序列中找到最长的和谐子序列的长度。数组的子序列是一个由数组派生出来的序列，它可以通过删除一些元素或不删除元素、且不改变其余元素的顺序而得到。

思路1_滑动窗口：数组排序，看右指针与左指针值的差，若大于1左指针动减小差值到1，若小于1右指针动增大差值到1，避免指针回溯。
思路2_map：数组排序，遍历数组以数为键记录数的个数，同时比较当前与上一个的数差是否为1记录个数和与max_len进行比较。(效果不如1)

3_643.子数组最大平均数（简单）

给你一个由 n 个元素组成的整数数组 nums 和一个整数 k 。请你找出平均数最大且 长度为 k 的连续子数组，并输出该最大平均数。任何误差小于 10-5 的答案都将被视为正确答案。

思路：以k为窗口大小移动，记录当前最大用于直接减去左窗口外加入右窗口新数据，变换一次比较最大（Double）。

4_1456.定长子串中元音的最大数目（中等）

给你字符串 s 和整数 k 。请返回字符串 s 中长度为 k 的单个子字符串中可能包含的最大元音字母数。英文中的 元音字母 为（a, e, i, o, u）。

思路：同3_643

5_2269_找到一个数字的K美丽值（简单）

一个整数 num 的 k 美丽值定义为 num 中符合以下条件的 子字符串 数目： 子字符串长度为 k 。 子字符串能整除 num 。 给你整数 num 和 k ，请你返回 num 的 k 美丽值。
输入：num = 240, k = 2。输出：2。 解释：以下是 num 里长度为 k 的子字符串：

• "240" 中的 "24" ：24 能整除 240 。
• "240" 中的 "40" ：40 能整除 240 。
  所以，k 美丽值为 2 。

思路：String与Int的转换，String的API

06_1984_学生分数的最小差值（简单）

给你一个 下标从 0 开始 的整数数组 nums ，其中 nums[i] 表示第 i 名学生的分数。另给你一个整数 k 。从数组中选出任意 k 名学生的分数，使这 k 个分数间 最高分 和 最低分 的 差值 达到 最小化 。返回可能的 最小差值 。

思路：排序后，以滑动窗口k,取最大最小比较

07_1343_大小为K且平均值大于等于阈值的子数组数目（中等）

给你一个整数数组 arr 和两个整数 k 和 threshold 。请你返回长度为 k 且 平均值大于等于 threshold 的子数组数目。

思路：以滑动窗口k,取值比较。

08_2090_半径为 k 的子数组平均值 1358（中等）

给你一个下标从 0 开始的数组 nums ，数组中有 n 个整数，另给你一个整数 k 。半径为 k 的子数组平均值 是指：nums 中一个以下标 i 为 中心 且 半径 为 k 的子数组中所有元素的平均值，即下标在 i - k 和 i + k 范围（含 i - k 和 i + k）内所有元素的平均值。如果在下标 i 前或后不足 k 个元素，那么 半径为 k 的子数组平均值 是 -1 。构建并返回一个长度为 n 的数组 avgs ，其中 avgs[i] 是以下标 i 为中心的子数组的 半径为 k 的子数组平均值 。x 个元素的 平均值 是 x 个元素相加之和除以 x ，此时使用截断式 整数除法 ，即需要去掉结果的小数部分。 例如，四个元素 2、3、1 和 5 的平均值是 (2 + 3 + 1 + 5) / 4 = 11 / 4 = 2.75，截断后得到 2 。

思路：指针i移动，符合半径大小的进行计算------>前缀和，之前的移动添减都可用前缀和来代替。

09_2379_得到 K 个黑块的最少涂色次数（简单）

给你一个长度为 n 下标从 0 开始的字符串 blocks ，blocks[i] 要么是 'W' 要么是 'B' ，表示第 i 块的颜色。字符 'W' 和 'B' 分别表示白色和黑色。 给你一个整数 k ，表示想要 连续 黑色块的数目。 每一次操作中，你可以选择一个白色块将它 涂成 黑色块。请你返回至少出现 一次 连续 k 个黑色块的 最少 操作次数。

思路：指针i移动，前缀和记录'W'个数，比较大小。

10_1052_ 爱生气的书店老板（中等）

有一个书店老板，他的书店开了 n 分钟。每分钟都有一些顾客进入这家商店。给定一个长度为 n 的整数数组 customers ，其中 customers[i] 是在第 i 分钟开始时进入商店的顾客数量，所有这些顾客在第 i 分钟结束后离开。在某些时候，书店老板会生气。 如果书店老板在第 i 分钟生气，那么 grumpy[i] = 1，否则 grumpy[i] = 0。当书店老板生气时，那一分钟的顾客就会不满意，若老板不生气则顾客是满意的。书店老板知道一个秘密技巧，能抑制自己的情绪，可以让自己连续 minutes 分钟不生气，但却只能使用一次。请你返回 这一天营业下来，最多有多少客户能够感到满意
输入：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.

思路：记录初始未生气人数，再计算以minutes为大小的窗口内最多生气人数，前缀和计算，返回两个之和。

11_2841_几乎唯一子数组的最大和（中等）

给你一个整数数组 nums 和两个正整数 m 和 k 。请你返回 nums 中长度为 k 的 几乎唯一 子数组的 最大和 ，如果不存在几乎唯一子数组，请你返回 0 。 如果 nums 的一个子数组有至少 m 个互不相同的元素，我们称它是 几乎唯一 子数组。子数组指的是一个数组中一段连续 非空 的元素序列。

思路：指针i移动维护一个窗口，记录下当前窗口内不重复数据和窗口内数据和，比较大小。 若要维护一个不重复的数组，可以选择set或者利用map对数据当键进行存储个数，cnt[nums[i]]++,cnt[nums[i]]--,若值为0可以移除

12_2461_长度为K子数组中的最大和（中等）

给你一个整数数组 nums 和一个整数 k 。请你从 nums 中满足下述条件的全部子数组中找出最大子数组和：子数组的长度是 k，且子数组中的所有元素 各不相同 。返回满足题面要求的最大子数组和。如果不存在子数组满足这些条件，返回 0 。子数组 是数组中一段连续非空的元素序列。

思路：指针i移动维护一个窗口，记录下当前窗口内不重复数据和窗口内数据和，比较大小。 若要维护一个不重复的数组，可以选择set或者利用map对数据当键进行存储个数，存储窗口内互不相同的数据，cnt[nums[i]]++,cnt[nums[i]]--,若值为0可以移除

13_1423_可获得的最大点数（中等）________1

几张卡牌 排成一行，每张卡牌都有一个对应的点数。点数由整数数组 cardPoints 给出。 每次行动，你可以从行的开头或者末尾拿一张卡牌，最终你必须正好拿 k 张卡牌。 你的点数就是你拿到手中的所有卡牌的点数之和。 给你一个整数数组 cardPoints 和整数 k，请你返回可以获得的最大点数。给你一个整数数组 nums 和一个整数 k 。请你从 nums 中满足下述条件的全部子数组中找出最大子数组和：子数组的长度是 k，且子数组中的所有元素 各不相同 。返回满足题面要求的最大子数组和。如果不存在子数组满足这些条件，返回 0 。子数组 是数组中一段连续非空的元素序列。

思路：求外层连续窗口的最大，即用总数减去内层连续窗口最小。

14_2134_最少交换次数来组合所有的1（中等）________1

环形 数组是一个数组，可以认为 第一个 元素和 最后一个 元素 相邻 。给你一个 二进制环形 数组 nums ，返回在 任意位置 将数组中的所有 1 聚集在一起需要的最少交换次数。

思路：（如何维护一个环形首尾相连数组的k大小窗口）（i%size()）求出最多个数1为k后，维护k大小窗口，查找所有窗口中0最少的。

15_2653_滑动子数组的美丽值（中等）________1

一个子数组的 美丽值 定义为：如果子数组中第 x 小整数 是 负数 ，那么美丽值为第 x 小的数，否则美丽值为 0 。请你返回一个包含 n - k + 1 个整数的数组，依次 表示数组中从第一个下标开始，每个长度为 k 的子数组的 美丽值 。 子数组指的是数组中一段连续 非空 的元素序列。

思路：维护k窗口内数据的排序，数组范围在[-50,50]，min，max不大，可以利用计数排序维护窗口内数据的排序（个人认为：空间换时间）

16_567_字符串的排列（中等）

给你两个字符串 s1 和 s2 ，写一个函数来判断 s2 是否包含 s1 的排列。如果是，返回 true 否则，返回 false 。

思路：在s2中维护一个s1大小的子窗口，由于判断的是随机排列，故记录窗口内的每个字符个数是否与s1中的每个字符个数相同，若相同则可以组合成s1,返回ture。

17_438_找到字符串中所有字符的异位词（中等）

给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。 异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。

思路：思路同16（vector可以直接==比较）

18_438_找到字符串中所有字符的异位词（困难）________1

给定整数 p 和 m ，一个长度为 k 且下标从 0 开始的字符串 s 的哈希值按照如下函数计算：hash(s, p, m) = (val(s[0]) * p0 + val(s[1]) * p1 + ... + val(s[k-1]) * pk-1) mod m.其中 val(s[i]) 表示 s[i] 在字母表中的下标，从 val('a') = 1 到 val('z') = 26 。给你一个字符串 s 和整数 power，modulo，k 和 hashValue 。请你返回 s 中 第一个 长度为 k 的 子串 sub ，满足 hash(sub, power, modulo) == hashValue 。测试数据保证一定 存在 至少一个这样的子串。子串 定义为一个字符串中连续非空字符组成的序列。

思路：1.秦九韶算法简化多项式计算，从n-k开始维护一个窗口，维护一个hash，窗口左移动维护hash值。2.每一次计算进行取余，不然太大存不下。

19_2953_找到字符串中所有字符的异位词（困难）________不会

思路：1.秦九韶算法简化多项式计算，从n-k开始维护一个窗口，维护一个hash，窗口左移动维护hash值。2.每一次计算进行取余，不然太大存不下。

2.不定长滑动窗口

左右两个指针根据情况动态分别移动

固定右端点求子数组个数（j-i+1）

类型：求最长，最短，恰好

01_3_无重复字符的最长字串（中等）

给定一个字符串 s ，请你找出其中不含有重复字符的 最长 子串 的长度。

思路：构建一个满足条件的初窗口，根据题意动态的分别移动窗口左右指针

02_1493_删掉一个元素以后全为1的最长子数组（中等）

给你一个二进制数组 nums ，你需要从中删掉一个元素。请你在删掉元素的结果数组中，返回最长的且只包含 1 的非空子数组的长度。如果不存在这样的子数组，请返回 0 。

思路：从0开始构建窗口，移动左右指针保证窗口内只有1个0

03_2730_找到最长的半重复子字符串（中等）

给你一个下标从 0 开始的字符串 s ，这个字符串只包含 0 到 9 的数字字符。

如果一个字符串 t 中至多有一对相邻字符是相等的，那么称这个字符串 t 是 半重复的 。例如，"0010" 、"002020" 、"0123" 、"2002" 和 "54944" 是半重复字符串，而 "00101022" （相邻的相同数字对是 00 和 22）和 "1101234883" （相邻的相同数字对是 11 和 88）不是半重复字符串。请你返回 s 中最长 半重复 子字符串 的长度。

思路：维护一个满足条件的窗口，当不满足same<=1时，从左指针i开始移动直到找到s[i]==s[i+1]，并移走s[i]后same=1，继续移动右指针。

04_904_水果成篮（中等）________1

你正在探访一家农场，农场从左到右种植了一排果树。这些树用一个整数数组 fruits 表示，其中 fruits[i] 是第 i 棵树上的水果 种类 。你想要尽可能多地收集水果。然而，农场的主人设定了一些严格的规矩，你必须按照要求采摘水果：

• 你只有 两个 篮子，并且每个篮子只能装 单一类型 的水果。每个篮子能够装的水果总量没有限制。
• 你可以选择任意一棵树开始采摘，你必须从 每棵 树（包括开始采摘的树）上 恰好摘一个水果 。采摘的水果应当符合篮子中的水果类型。每采摘一次，你将会向右移动到下一棵树，并继续采摘。
• 一旦你走到某棵树前，但水果不符合篮子的水果类型，那么就必须停止采摘。

给你一个整数数组 fruits ，返回你可以收集的水果的 最大 数目。

思路：从0开始维护一个有两种树的窗口用map记录个数，当右指针移动到（cnt[fruits[j]]++），出现第三种树时（cnt.size()>2），左指针移动缩小窗口直到原来的两种树有其中一种没有（cnt[fruits[i]]==0），并删除掉cnt.erase[fruits[i]]。

05_1695_删除子数组的最大得分（中等）

给你一个正整数数组 nums ，请你从中删除一个含有 若干不同元素 的子数组**。**删除子数组的 得分 就是子数组各元素之 和 。返回 只删除一个 子数组可获得的 最大得分 *。*如果数组 b 是数组 a 的一个连续子序列，即如果它等于 a[l],a[l+1],...,a[r] ，那么它就是 a 的一个子数组。

思路：从0开始维护一个窗口，map记录里面的数，右指针加入窗口，若已经出现过次数为2，左指针一直移动缩减窗口，直到将此出现个数减少为1。类似05

06_2958_最多K个重复元素的最长子数组（中等）

给你一个整数数组 nums 和一个整数 k 。一个元素 x 在数组中的 频率 指的是它在数组中的出现次数。如果一个数组中所有元素的频率都 小于等于 k ，那么我们称这个数组是 好 数组。请你返回 nums 中 最长好 子数组的长度。子数组 指的是一个数组中一段连续非空的元素序列。

思路：从0开始维护一个窗口，右指针每移动一个进窗口，记录移入数后是否满足cnt[nums[j]]<k，不满足则左指针移动缩小窗口，直到将此出现个数减少为k。类似05

07_2024_考试的最大困扰度（中等）

一位老师正在出一场由 n 道判断题构成的考试，每道题的答案为 true （用 'T' 表示）或者 false （用 'F' 表示）。老师想增加学生对自己做出答案的不确定性，方法是 最大化 有 连续相同 结果的题数。（也就是连续出现 true 或者连续出现 false）。

给你一个字符串 answerKey ，其中 answerKey[i] 是第 i 个问题的正确结果。除此以外，还给你一个整数 k ，表示你能进行以下操作的最多次数：

• 每次操作中，将问题的正确答案改为 'T' 或者 'F' （也就是将 answerKey[i] 改为 'T' 或者 'F' ）。

请你返回在不超过 k 次操作的情况下，最大 连续 'T' 或者 'F' 的数目。

思路：保持窗口内，T或F两种的个数不全大于k，若有，左指针移动缩小窗口，直到将T或F出现个数减少为k。（即可对少的（肯定小于k次）进行操作变为多的）

08_1004_最大连续1的个数（中等）

给定一个二进制数组 nums 和一个整数 k，如果可以翻转最多 k 个 0 ，则返回 数组中连续 1 的最大个数 。

思路：相比07一样，将TF看做01，本题只用考虑转换0一种情况。

09_1438_绝对差不超过限制的最长连续子数组（中等）__1

给你一个整数数组 nums ，和一个表示限制的整数 limit，请你返回最长连续子数组的长度，该子数组中的任意两个元素之间的绝对差必须小于或者等于 limit *。*如果不存在满足条件的子数组，则返回 0 。

思路：维护窗口最大最小值（多个相同最大/最小值）。遇到不满足条件时缩减窗口更换最大最小值直到满足。可以：

• multiset（int） s; s.begin() s.rbegin()获取最大最小值地址（移动左指针删除时 cnt.erase(s.find(nums[i++]));）。
• deque（int） minq,maxq; 维护一个双端队列。有新元素时从尾部依次将比他小/大的从后面pop_bcak，最后将新元素push_back。（队列循环时加条件!minq.empty()判空）。
• map<int,int>也是有序

10_2401_最长优雅子数组（中等）__?

给你一个由 正 整数组成的数组 nums 。如果 nums 的子数组中位于 不同 位置的每对元素按位 **与（AND）**运算的结果等于 0 ，则称该子数组为 优雅 子数组。返回 最长 的优雅子数组的长度。子数组 是数组中的一个 连续 部分。**注意：**长度为 1 的子数组始终视作优雅子数组。

思路：用^计算？？？？

11_1658_将x减到0的最小操作数（中等）

给你一个整数数组 nums 和一个整数 x 。每一次操作时，你应当移除数组 nums 最左边或最右边的元素，然后从 x 中减去该元素的值。请注意，需要 修改 数组以供接下来的操作使用。如果可以将 x 恰好 减到 0 ，返回 最小操作数 ；否则，返回 -1 。

思路：将操作两边的问题转化为内部窗口问题，求两边最少个数满足x，即求内部最多个数满足sum-x

12_1838_最高频元素的频数（中等）__1

元素的 频数 是该元素在一个数组中出现的次数。给你一个整数数组 nums 和一个整数 k 。在一步操作中，你可以选择 nums 的一个下标，并将该下标对应元素的值增加 1 。执行最多 k 次操作后，返回数组中最高频元素的 最大可能频数 。

思路：没有说是子数组，不要目标连续，求的也是与大小有关可以考虑先排序。后面的就是普通不定长窗口问题。

13_2516_每种字符至少取 K 个（中等）

给你一个由字符 'a'、'b'、'c' 组成的字符串 s 和一个非负整数 k 。每分钟，你可以选择取走 s 最左侧 还是 最右侧 的那个字符。

你必须取走每种字符 至少 k 个，返回需要的 最少 分钟数；如果无法取到，则返回 -1 。

思路：边界操作转换为内部窗口操作（类11）。字母表计可以用vector不要用map更省时。

14_2831_找出最长等值子数组（中等）__2

给你一个下标从 0 开始的整数数组 nums 和一个整数 k 。如果子数组中所有元素都相等，则认为子数组是一个 等值子数组 。注意，空数组是 等值子数组 。从 nums 中删除最多 k 个元素后，返回可能的最长等值子数组的长度。子数组 是数组中一个连续且可能为空的元素序列。

思路：利用vector<vector（int）> pos_x结构存储nums中每一类数的pos下标

***（例如nums中的数m，可以通过pos_x计算出nums中从第一个m到最后一个m之间共有几个数，有几个m，相减得到除m外有几个数，并以此为窗口移动左指针减少m个数从而减少不是m的数的个数）

对pos_x进行遍历，得到pos_x中每一个vector作为窗口进行while寻找能满足题意条件的值（不满足就移动pos_x中vector的左指针），最后取最大。

15_209_长度最小的子数组（中等）

给定一个含有 n 个正整数的数组和一个正整数 target **。找出该数组中满足其总和大于等于 target 的长度最小的 子数组[numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。**如果不存在符合条件的子数组，返回 0 。

思路：求最小时和求最大类似，维护窗口然后根据题意移动左指针（但是移动左指针思路不同于求最大）。本题目标求窗口总和最小的最短子数组，维护窗口内值小于target，当加入新的大于target时移动左指针使其小于。

16_1234_替换子串得到平衡字符串（中等）__1

有一个只含有 'Q', 'W', 'E', 'R' 四种字符，且长度为 n 的字符串。假如在该字符串中，这四个字符都恰好出现 n/4 次，那么它就是一个「平衡字符串」。 给你一个这样的字符串 s，请通过「替换一个子串」的方式，使原字符串 s 变成一个「平衡字符串」。你可以用和「待替换子串」长度相同的 任何 其他字符串来完成替换。请返回待替换子串的最小可能长度。如果原字符串自身就是一个平衡字符串，则返回 0。

思路：因为总数可以被4整除，这个串必定可以被处理成平衡字符串（qwe每一个r必定可以被转换为n/4个）。故只需要找到一个字串，使得此字串外的qwer个数是小于n/4，这样就可处理那个字串使其变为平衡字符串。

17_最短超串（中等）

假设你有两个数组，一个长一个短，短的元素均不相同。找到长数组中包含短数组所有的元素的最短子数组，其出现顺序无关紧要。返回最短子数组的左端点和右端点，如有多个满足条件的子数组，返回左端点最小的一个。若不存在，返回空数组。

思路：关键在用什么数据结构记录small所需是否被满足。只用map，每一次都要遍历是否全<=0，可以加入need维护map的value值，加入或移出元素根据情况操作need，不用每次通过遍历验证满足情况。

代码思路：

利于map存small数组元素个数（需要的个数满足条件），用need存储还需要的个数。对big进行滑动窗口：

进入元素，如果元素属于small，map[ big[j] ]--，若窗口内还需要此元素（可能窗口内有多个此元素看之前的是否能满足small对于此元素的要求若还需要），进行need--表示又满足了一个。

当need==0时满足条件了，取一组ij后左指针移动缩减窗口求最小。

对于移出元素，若元素属于small，map[big[i]]++ , 若移出后使窗口不满足条件（cnt[big[i]]>0）进行need++。

18_76_最小覆盖字串（困难）

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。

思路：同17

19_1574_删除最短子数组使剩余数组有序（中等）__2

给你一个整数数组 arr ，请你删除一个子数组（可以为空），使得 arr 中剩下的元素是 非递减 的。一个子数组指的是原数组中连续的一个子序列。请你返回满足题目要求的最短子数组的长度。

思路：理解为找一个最长的递增数组。

• 先找到数组左边最大递增数组，初始化ans=j
• 然后从左边i=0开始枚举每一个元素，for循环必须满足arr[i]>arr[i-1]（i==0时除外），若不满足此条件则往后的不能连续，直接停止寻找返回答案。
• 若左边数组是递增的，但是arr[i]>=arr[j]，j指针后移。

20_2799_统计完全子数组个数（中等）

给你一个由 正 整数组成的数组 nums 。如果数组中的某个子数组满足下述条件，则称之为 完全子数组 ：子数组中 不同 元素的数目等于整个数组不同元素的数目。返回数组中 完全子数组 的数目。子数组 是数组中的一个连续非空序列。

思路：模板。求所有要和只求最大最小不同，每求得一个，以此i为基准把j拉到最长，再退回j。移动i++找下一个。此题不用拉长，因为当前窗口满足则以此i为基地往后所有都满足，只用计算后直接移动i

21_713_ 乘积小于 K 的子数组（中等）__1

给你一个整数数组 nums 和一个整数 k ，请你返回子数组内所有元素的乘积严格小于 k 的连续子数组的数目。

思路：窗口i,j。其中的夹杂的元素个数与子窗口个数都为j-i+1，当一个窗口满足条件后，每一个子窗口都满足条件。此为固定右端点求子数组个数。可避免重复加窗口。

例如，假设当前 i = 2，j = 5，那么以 j = 5 为右边界的有效子数组有 [nums[5]], [nums[4], nums[5]], [nums[3], nums[4]，nums[5], [nums[2], nums[3], nums[4], nums[5]]，这些子数组的数量就是 5 - 2 + 1 = 4。

找到一个符合的窗口，累加获得子窗口个数。

22_1358_包含所有三种字符的子字符串数目（中等）

给你一个字符串 s ，它只包含三种字符 a, b 和 c 。请你返回 a，b 和 c 都 至少 出现过一次的子字符串数目。

思路：和20类似，只要当前窗口满足则以此i为开始的窗口往后都满足，得到后只用移动i找不同起点窗口即可。

23_1962_统计最大元素出现至少 K 次的子数组（中等）

给你一个整数数组 nums 和一个 正整数 k 。请你统计有多少满足 「 nums 中的 最大 元素」至少出现 k 次的子数组，并返回满足这一条件的子数组的数目。子数组是数组中的一个连续元素序列。

思路：模板。只要以i为起点第一个最小窗口满足，后面延长窗口都满足.（size()-j）。只用移动i找每个以i为起点的最小窗口。

24_2302_统计得分小于 K 的子数组数目（困难）

一个数组的 分数 定义为数组之和 乘以 数组的长度。比方说，[1, 2, 3, 4, 5] 的分数为 (1 + 2 + 3 + 4 + 5) * 5 = 75 。给你一个正整数数组 nums 和一个整数 k ，请你返回 nums 中分数 严格小于 k 的 非空整数子数组数目。子数组 是数组中的一个连续元素序列。

思路：类似21。当一个窗口满足条件后，每一个子窗口都满足条件，但是为了避免加到重复子窗口，对每个符合窗口求以右端点为固定求子窗口个数。

25_2537_统计好子数组的数目（中等）

给你一个整数数组 nums 和一个整数 k ，请你返回 nums 中 好 子数组的数目。一个子数组 arr 如果有 至少 k 对下标 (i, j) 满足 i < j 且 arr[i] == arr[j] ，那么称它是一个 好 子数组。子数组 是原数组中一段连续 非空 的元素序列。

思路：以什么方式来统计有几对。用numz记录当前窗口对数，用map计数，进入元素统计之前是否有这个元素了，当元素个数>=2时进行numz+=cnt[nums[j]]-1（前面有几个相同的就会多几对，移动i减少对数也是这样）。当当前窗口有两对后，以此i为起点后面的窗口都是满足的。

26_2762_不间断数组（中等）__1

思路：只要窗口内最大最小值满足条件即可，内部所有子数组满足，（如何维护窗口内多个最大最小值（queue或multiset或map（删除时cnt.erase(s.find(nums[i++]));）））。

27_2972_ 统计移除递增子数组的数目（困难）__2

给你一个下标从 0 开始的 正 整数数组 nums 。如果 nums 的一个子数组满足：移除这个子数组后剩余元素 严格递增 ，那么我们称这个子数组为 移除递增 子数组。比方说，[5, 3, 4, 6, 7] 中的 [3, 4] 是一个移除递增子数组，因为移除该子数组后，[5, 3, 4, 6, 7] 变为 [5, 6, 7] ，是严格递增的。请你返回 nums 中 移除递增 子数组的总数目。注意 ，剩余元素为空的数组也视为是递增的。子数组 指的是一个数组中一段连续的元素序列。

思路：

28_930_和相同的二元子数组（中等）(子数组内"刚好")__1

给你一个二元数组 nums ，和一个整数 goal ，请你统计并返回有多少个和为 goal 的 非空 子数组。子数组 是数组的一段连续部分。

思路：理解为 大窗口-小窗口 概念

方法一：前缀和+hash。枚举右指针 j，j下标元素的前缀和为pre[j]。假设0~j有子窗口（定j为右窗边）使得窗口和为goal，则此窗口内和为pre[j+1]-pre[i]=goal（大窗-小窗）。goal和pre[j+1]已知就只用求出pre[i]并求pre[i]的个数即满足条件的子数组。用hash表存每个元素的前缀和。（初始化时初始一个前缀和0，cnt[0]++）

方法二：滑动窗口。右指针 j，满足 sum[j]−sum[i]=goal 的 i 总是落在一个连续的区间中，i 值取区间中每一个数都满足条件。并且随着 j 右移，其对应的区间的左右端点也将右移。

29_1248_统计「优美子数组」（中等）

给你一个整数数组 nums 和一个整数 k。如果某个连续子数组中恰好有 k 个奇数数字，我们就认为这个子数组是「优美子数组」。请返回这个数组中 「优美子数组」 的数目。

思路：同28，求子数组内刚好某个条件的个数。

30_2563_统计公平数对的数目（中等）__1

给你一个下标从 0 开始、长度为 n 的整数数组 nums ，和两个整数 lower 和 upper ，返回 公平数对的数目 。

如果 (i, j) 数对满足以下情况，则认为它是一个 公平数对 ：0 <= i < j < n，且lower <= nums[i] + nums[j] <= upper

思路：二分查找。枚举右指针j，只用找到0~j区间内的满足lower和upper条件的left与right下标，求得个数加上。

枚举 nums[j]，那么 nums[i] 需要满足lower−nums[j]≤nums[i]≤upper−nums[j]，并且 0≤i<j。

我们可以计算出 ≤upper−nums[j] 的元素个数，减去 <lower−nums[j] 的元素个数，加入答案。

二、二分查找

二分查找可分为以下：

​ //14479

• 找到第一个>=target的数
• 找到最后一个<=target的数（找到第一个>=target+1的数-1）
• 找到第一个>target的数（找到第一个>=target+1的数）
• 找到最后一个<target的数（找到第一个>=target的数）

后三个都可通过求第一>=的模式求出。

1.普通题

01_34_在排序数组中查找元素的第一个和最后一个位置（中等）

给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。如果数组中不存在目标值 target，返回 [-1, -1]。

思路：二分查找。注意判断必须是等于target。

02_1385_两个数组间的距离值（简单）

给你两个整数数组 arr1 ， arr2 和一个整数 d ，请你返回两个数组之间的 距离值 。「距离值」 定义为符合此距离要求的元素数目：对于元素 arr1[i] ，不存在任何元素 arr2[j] 满足 |arr1[i]-arr2[j]| <= d 。

思路：|arr1[i]-arr2[j]| > d ，arr2排序后，找到第一个<arr1[i]，第一个>=arr1[i]，同时满足，arr2是有序的，则往后的都满足。（注意：可能没有<arr1[i]或>=arr1[i]的，注意判断如何写（不存在时则不用判断那一方））

if((a1==-1||abs(arr1[i] - arr2[a1]) > d)&&(a2==l||abs(arr1[i] - arr2[a2]) > d))
ans++;

03_2300_咒语和药水的成功对数（中等）

给你两个正整数数组 spells 和 potions ，长度分别为 n 和 m ，其中 spells[i] 表示第 i 个咒语的能量强度，potions[j] 表示第 j 瓶药水的能量强度。同时给你一个整数 success 。一个咒语和药水的能量强度 相乘 如果 大于等于 success ，那么它们视为一对 成功 的组合。请你返回一个长度为 n 的整数数组 pairs，其中 pairs[i] 是能跟第 i 个咒语成功组合的 药水 数目。

思路：枚举spells，对排序后的potions找到第一个>=success/spells[i]的，注意向上取整，后面的都满足。

04_2389_和有限的最长子序列（简单）

给你一个长度为 n 的整数数组 nums ，和一个长度为 m 的整数数组 queries 。返回一个长度为 m 的数组 answer ，其中 answer[i] 是 nums 中 元素之和小于等于 queries[i] 的 子序列 的 最大 长度 。子序列 是由一个数组删除某些元素（也可以不删除）但不改变剩余元素顺序得到的一个数组。

思路：枚举queries[i]，将nums排序后求前缀和，找到最后一个>=queries[i]

05_1170_比较字符串最小字母出现频次（中等）

定义一个函数 f(s)，统计 s 中**（按字典序比较）最小字母的出现频次** ，其中 s 是一个非空字符串。例如，若 s = "dcce"，那么 f(s) = 2，因为字典序最小字母是 "c"，它出现了 2 次。现在，给你两个字符串数组待查表 queries 和词汇表 words 。对于每次查询 queries[i] ，需统计 words 中满足 f(queries[i]) < f(W) 的 词的数目 ，W 表示词汇表 words 中的每个词。请你返回一个整数数组 answer 作为答案，其中每个 answer[i] 是第 i 次查询的结果。

思路：先处理words中每一个string获得最小字母出现次数，将次数数组v进行排序。然后枚举queries中的每个string，并得到最小字母出现次数，找到v中第一个>此出现次数的，计算个数。

06_2080_区间内查询数字的频率（中等）__1

请你设计一个数据结构，它能求出给定子数组内一个给定值的 频率 。子数组中一个值的 频率 指的是这个子数组中这个值的出现次数。请你实现 RangeFreqQuery 类：

• RangeFreqQuery(int[] arr) 用下标从 0 开始的整数数组 arr 构造一个类的实例。
• int query(int left, int right, int value) 返回子数组 arr[left...right] 中 value 的 频率 。

一个 子数组 指的是数组中一段连续的元素。arr[left...right] 指的是 nums 中包含下标 left 和 right 在内 的中间一段连续元素。 示例 1：

输入：
["RangeFreqQuery", "query", "query"]
[[[12, 33, 4, 56, 22, 2, 34, 33, 22, 12, 34, 56]], [1, 2, 4], [0, 11, 33]]
输出：
[null, 1, 2]

思路：利用map<int,vector（int）> pos维护每个元素出现的下标，在query函数中，根据left和right计算出此元素的下标数组中，第一个>=left和第一个>right的，下标r,l，将此作差得到在arr中left和right区间中的下标个数即元素个数。注意：

auto& arr = it->second; // 这样写直接引用原数组，直接访问或不写引用会进行一次copy，导致超时。

07_2856_删除数对后的最小数组长度（中等）___2

给你一个下标从 0 开始的 非递减 整数数组 nums 。你可以执行以下操作任意次：

• 选择 两个 下标 i 和 j ，满足 nums[i] < nums[j] 。
• 将 nums 中下标在 i 和 j 处的元素删除。剩余元素按照原来的顺序组成新的数组，下标也重新从 0 开始编号。

请你返回一个整数，表示执行以上操作任意次后（可以执行 0 次），nums 数组的 最小 数组长度。

思路： 首先，找出重复最多的元素，将其与剩下的元素分为AB两组，A组的元素只能与B组的元素对应消除。

​ 1.若a>=b，则a个全可以两两把b内的消除，剩下的a相同并不能

​ 2.若a<b，当b-a为偶数，剩下的可以两两消除，反之若为奇数，会剩一个

08_1283_使结果不超过阈值的最小除数（中等）__1

给你一个整数数组 nums 和一个正整数 threshold ，你需要选择一个正整数作为除数，然后将数组里每个数都除以它，并对除法结果求和。请你找出能够使上述结果小于等于阈值 threshold 的除数中 最小 的那个。每个数除以除数后都向上取整，比方说 7/3 = 3 ， 10/2 = 5 。题目保证一定有解。

思路：最小为1，最大为nums中的max。在此范围中二分查找求满足条件的第一个满足条件的。

09_2187_完成旅途的最少时间（中等）

给你一个数组 time ，其中 time[i] 表示第 i 辆公交车完成 一趟****旅途 所需要花费的时间。每辆公交车可以 连续 完成多趟旅途，也就是说，一辆公交车当前旅途完成后，可以 立马开始 下一趟旅途。每辆公交车 独立 运行，也就是说可以同时有多辆公交车在运行且互不影响。给你一个整数 totalTrips ，表示所有公交车 总共 需要完成的旅途数目。请你返回完成 至少 totalTrips 趟旅途需要花费的 最少 时间。

思路：找到一个时间的范围，进行二分查找，找到第一个满足条件的时间。

10_1870_准时到达的列车最小时速（中等）

给你一个浮点数 hour ，表示你到达办公室可用的总通勤时间。要到达办公室，你必须按给定次序乘坐 n 趟列车。另给你一个长度为 n 的整数数组 dist ，其中 dist[i] 表示第 i 趟列车的行驶距离（单位是千米）。

每趟列车均只能在整点发车，所以你可能需要在两趟列车之间等待一段时间。

• 例如，第 1 趟列车需要 1.5 小时，那你必须再等待 0.5 小时，搭乘在第 2 小时发车的第 2 趟列车。

返回能满足你准时到达办公室所要求全部列车的 最小正整数 时速（单位：千米每小时），如果无法准时到达，则返回 -1 。生成的测试用例保证答案不超过 107 ，且 hour 的 小数点后最多存在两位数字 。

思路：找到速度范围，二分查找第一个满足条件的时间。

11_1011_在 D 天内送达包裹的能力（中等）

传送带上的包裹必须在 days 天内从一个港口运送到另一个港口。传送带上的第 i 个包裹的重量weights[i]。每一天，我们都会按给出重量（weights）的顺序往传送带上装载包裹。我们装载的重量不会超过船的最大运载重量。返回能在 days 天内将传送带上的所有包裹送达的船的最低运载能力。

思路：找到能力范围，不能小于最大包裹的重量，最大在一天送完所有，然后二分找第一个满足条件的值。

12_875_爱吃香蕉的珂珂（中等）

珂珂喜欢吃香蕉。这里有 n 堆香蕉，第 i 堆中有 piles[i] 根香蕉。警卫已经离开了，将在 h 小时后回来。珂珂可以决定她吃香蕉的速度 k （单位：根/小时）。每个小时，她将会选择一堆香蕉，从中吃掉 k 根。如果这堆香蕉少于 k 根，她将吃掉这堆的所有香蕉，然后这一小时内不会再吃更多的香蕉。 珂珂喜欢慢慢吃，但仍然想在警卫回来前吃掉所有的香蕉。返回她可以在 h 小时内吃掉所有香蕉的最小速度 k（k 为整数）。

思路：找每小时吃的范围：1~max_element(piles)，然后二分找，找个数时用除法。

13_475_供暖器（中等）__1

冬季已经来临。 你的任务是设计一个有固定加热半径的供暖器向所有房屋供暖。在加热器的加热半径范围内的每个房屋都可以获得供暖。现在，给出位于一条水平线上的房屋 houses 和供暖器 heaters 的位置，请你找出并返回可以覆盖所有房屋的最小加热半径。注意：所有供暖器 heaters 都遵循你的半径标准，加热的半径也一样。

思路：主要在于，check函数检验是否能供暖所有，枚举房屋，并有j指针指向heaters，当前j指向的heaters不满足当前枚举的房屋时，j指针后移直到满足或超出heaters范围，循环结束后检查，若超出范围或仍然不满足则无法供暖所有。

14_275._H指数II（中等）

给你一个整数数组 citations ，其中 citations[i] 表示研究者的第 i 篇论文被引用的次数，citations 已经按照 升序排列 。计算并返回该研究者的 h 指数。h 指数的定义：h 代表“高引用次数”（high citations），一名科研人员的 h 指数是指他（她）的 （n 篇论文中）至少 有 h 篇论文分别被引用了至少 h 次。 请你设计并实现对数时间复杂度的算法解决此问题。

思路：确定要找的是最少的h篇（数组下标即为第几个论文）论文，然后看这h篇论文是否满足都至少被引用了h次。论文篇数即下标是有序的，则二分找论文个数（0，size()），check函数判断：当前mid的引用次数（h篇论文里面的即最小引用次数）>= 当前位置往后的论文个数h=(size()-mid)。

15_2226. 每个小孩最多能分到多少糖果（中等）__1

给你一个 下标从 0 开始 的整数数组 candies 。数组中的每个元素表示大小为 candies[i] 的一堆糖果。你可以将每堆糖果分成任意数量的 子堆 ，但 无法 再将两堆合并到一起。 另给你一个整数 k 。你需要将这些糖果分配给 k 个小孩，使每个小孩分到 相同 数量的糖果。每个小孩可以拿走 至多一堆 糖果，有些糖果可能会不被分配。 返回每个小孩可以拿走的 最大糖果数目 。

思路：找最大数目，与找最小相反（二分时判断若不满足条件right左移，最后结果返回right）。此题重点在check糖果数目为mid时，如何看是否够分。遍历candies，sum+=candies[i]/mid；

16_3143_正方形中最多点数（中等）__1

给你一个二维数组 points 和一个字符串 s ，其中 points[i] 表示第 i 个点的坐标，s[i] 表示第 i 个点的 标签 。如果一个正方形的中心在 (0, 0) ，所有边都平行于坐标轴，且正方形内 不 存在标签相同的两个点，那么我们称这个正方形是 合法 的。请你返回 合法 正方形中可以包含的 最多 点数。**注意：**如果一个点位于正方形的边上或者在边以内，则认为该点位于正方形内。正方形的边长可以为零

思路：包含最多点数和正方形大小是成正比的，故对正方形大小进行二分查找，用一个全局变量记录最大答案，check函数内用大小为mid的正方形对point进行遍历，若出现point在正方形内且有重复的（hashmap记录）则这个大小的正方形不满足，一直到找到一个最大的满足条件的正方形。

17_2064._分配给商店的最多商品的最小值（中等）

给你一个整数 n ，表示有 n 间零售商店。总共有 m 种产品，每种产品的数目用一个下标从 0 开始的整数数组 quantities 表示，其中 quantities[i] 表示第 i 种商品的数目。你需要将 所有商品 分配到零售商店，并遵守这些规则：

• 一间商店 至多 只能有 一种商品 ，但一间商店拥有的商品数目可以为 任意 件。
• 分配后，每间商店都会被分配一定数目的商品（可能为 0 件）。用 x 表示所有商店中分配商品数目的最大值，你希望 x 越小越好。也就是说，你想 最小化 分配给任意商店商品数目的 最大值 。

请你返回最小的可能的 x 。

思路：就是求最小的满足分配条件的数。二分找第一个满足条件的。