【LeetCode 846. 一手顺子】
思路：有两大类，一类使用有序哈希表 map ，一类使用排序。
map 的键是不重复的，所以计数的是它的值；排序后的数组相邻下标存放的数值可能是一样的，所以需要再申请一个同样大小的数组（这里不需要申请变长数组）记录是否被访问。
先来看 map 的思路：
如果 数组的长度 不可以整除 给出的子组长，那么一定不可能分组成功；
使用有序哈希表 count 是因为题目要求数值连续，遍历 hand 数组，count 计数;
期望的情况下，如果成功分组，count 应该为空，因为每个 key 的次数都被用光并擦除；
在每轮分组的过程中，可能失败的情况：在子组长内，无法找到匹配的 key ；
分组过程中，用掉了一次 key 后，判断 key 的剩余次数，如果为 0 ，那么将 key 键值对从 count 中擦去；
补充知识点：
map.end() ：感觉像是最后一个元素后继的空节点。
map.begin()->first：map中的第一个元素（有指向 first 才能取出元素，不然返回的是迭代器）
实现过程：
检查数组长度是否符合期望：
int n = hand.size();
if (n % groupSize) return false;
申请有序哈希表 count ，遍历 hand 计数：
map<int , int> count;
for (auto x : hand) count[x] ++;
当 count 没有被擦光时，进行分组；每次分组以当前 count 中最小值为开始（ for 循环中的计数减一和擦除判断 ，开始值都需要进行，所以 for 循环从开始值开始）。
while (count.size()) {
int start = count.begin()->first;
for (int i = start; i < start + groupSize; i++) {
if (count.find(i) == count.end()) return false;
if (!--count[i]) count.erase(i);
}
}
如果分组成功，返回 true；
return true;
提交总览：
至此，有序哈希表的方法结束。
接下来，看排序的方法：
先对数组进行排序，同时申请一个同样大小的数组记录是否访问；
每次分组从未被访问的第一个元素开始，每次成功向后访问一个元素，就将该元素对应的访问记录修改为已访问；
分组过程中，可能失败的情况：下一个不重复的值与该值不连续；
最后一次分组结束后，如果累计的访问长度小于子组长，失败；
实现：
数组长不能整除子组长，一定失败；
子组长为一，一定成功；
int n = hand.size();
if (n % groupSize) return false;
if (groupSize == 1) return true;
对原数组进行排序；申请一个访问记录，这里使用的是变长数组赋初值 0 （定长数组赋初值不是很方便，特别是在赋 !0 值的情况下，可以了解一下 fill 函数）
sort(hand.begin() , hand.end());
vector<int> visit(n, 0);
每一轮分组过程中，累计的子组访问长度的初始值为 1 ；将访问的初始值的访问记录赋值为已访问；向后寻找不重复的第一个值，如果不符合累计长度的要求，失败；如果符合，累计长度加一，该值的访问记录赋值为已访问；如果 累计访问长度 等于 子组长 ，开始下一次的子组分组；
int cnt = 1;
visit[i] = 1;
for (int j = i + 1; j < n; j++) {
if (hand[j] > hand[i] + cnt) break;
if (!visit[j] && hand[j] == hand[i] + cnt) {
visit[j] = 1;
cnt ++;
if (cnt == groupSize) break;
}
最后一次分组，可能存在累计访问长度不等于子组长的情况，此时失败；
if (cnt != groupSize) return false;
完整的外层 for 循环代码：
for (int i = 0; i < n; i++) {
if (!visit[i]) {
int cnt = 1;
visit[i] = 1;
for (int j = i + 1; j < n; j++) {
if (hand[j] > hand[i] + cnt) break;
if (!visit[j] && hand[j] == hand[i] + cnt) {
visit[j] = 1;
cnt ++;
if (cnt == groupSize) break;
}
}
if (cnt != groupSize) return false;
}
}
如果成功分组，返回 true ;
return true;
提交总览：
至此，排序算法结束；
其实排序算法不止这一种思路，比如还有一个思路：快速排序后，根据遍历的前面的数量来计算后面牌的期望数量，不过这个方法的空间复杂度和时间复杂度没有优于上述这种排序方法，虽然思路很有创意，但是也不能算得上简单，所以此处不再记录。
【LeetCode 1248. 统计「优美子数组」】
这道题有三个思路：
1）统计奇数位置
2）双指针
3）前缀和
先来看统计奇数位置的思路：
（ 可以把奇数都看作 1 ，偶数都看作 0 ）
满足题目条件的子数组有 k 个 1，以第一个 1 和最后一个 1 为子数组的俩道分界线，中间段（包括两端的 1 ）包含了 k 个 1 ，两端都是 0 。假设首端有 h 个 0 ，末端有 g 个 0 ，首端可以取 0 到 h 个 0 ，末端可以取 0 到 g 个 0 。所以对于这种中间段，一共有 (h + 1) * (g + 1) 种组合方式。
那么如何计算 h 和 g 呢？
已知首端的右边界是中间段的最左边的 1（下标j0） 之前，那么首端的左边界就是整个数组左部与中间段的最左边的 1 最靠近的 1 （下标 j1）。同理，末端的右边界是整个数组右部与中间段的最右边的 1（下标j2） 最靠近的 1（下标j3） 。如果将数组中每个 1 的位置存储到一个数组里， 那么 （h + 1）和（g + 1）就非常好计算了。
h + 1 = j1 - j0
g + 1 = j3 - j2
接下来，实现这个存储了奇数下标的数组。那么 j1 实际上给就是 j0 的后面一个，j3 是 j2 起（包括 j2 ）的第 k 个元素。
pos_j1 = pos_j0 + 1;
pos_j3 = pos_j2 + (k - 1);
最后考虑边界值情况：
如果整个数组中最左边的 1 （下标 i0）不在第一位上，那么最左边的 1 的左边有多少个 0 呢？
其实思考方式和上面是一样的。把整个数组中最左边的 1 当作是中间段的左界，需要寻找的就是首端的左界，如果在数组的第一个元素（0）之前假设存在一个非零的数，那么这个数就可以当作左界。这个数的下标是 -1 ，在存入后续 1 的位置之前，先将 -1 push 进去。同理，在考虑最后一个位置的值不是 1 时，需要寻找右界，右界就是在数组的最后一个元素（0）之后假设存在一个非零的数，那么这个数就可以当作右界。这个数的下标是 n ，将整个数组的 1 的位置都存储后，再将 n push 进去。
代码实现：
获取数组长度；
int n = nums.size();
申请存储 1 和边界值情况的下标的数组；
vector<int> pos;
左界 push；
pos.push_back(-1);
每个 1 的下标 push ;
for (int i = 0; i < n; i++) {
if (nums[i] % 2 == 1) pos.push_back(i);
}
右界 push ;
pos.push_back(n);
带入表达式，累加；
int res = 0;
for (int j = 1; j + k < pos.size(); j++) {
res += (pos[j] - pos[j - 1]) * (pos[j + k] - pos[j + k - 1]);
}
返回遍历结束后的累加值；
return res;
提交总览：
至此，统计奇数位置的思路结束。
接下来，思考双指针的思路：
一共有多少个符合条件的子数组可以转化为计算每个满足右界不超过数组边界的子数组的个数，再求和。每个子数组又可以转化为以首个 1 的位置为基准的数组，求这样的子数组的个数就是求首个 1 左侧能放多少个 0 。
例如，最初的情况下，左右指针都指向下标 0 ，先移动右指针找到满足条件的子数组的最右边的 1 的下标。接下来移动左指针，同时计数，直到遇见 1 。此时的计数结果就是该子数组的所有可能。
那么为什么这种看法只需要看左边，而不需要看右边呢？因为如果看右边，其实相当于计数了以与子数组的最右边的 1 相邻的下一个 1为基准的子数组的所有可能。所以不需要考虑右边，后续会遍历到的。
那么怎么推动遍历呢？ 就是将刚刚计数为 k 的值减一，当计数小于 k 时，就会寻找下一个 1 ，那么左指针就会开始下一轮的移动和 0 的计数。
代码实现：
申请返回值，子数组中 1 的计数，子数组的可能数，左指针（用于确定可能数），右指针（用于推动遍历）；
int res = 0;
int cnt = 0;
int even = 0;
int l = 0;
int r = 0;
向后寻找符合条件的子数组；
if (cnt < k && nums[r++] % 2 == 1) cnt ++;
移动左指针并统计 0 的个数（该子数组的可能数）；（注意这里是需要上一段代码的运行结果的，不可以用 else if ）
if (cnt == k) {
even = 1;
while (!(nums[l++] % 2)) even ++;
cnt --;
}
累加每类子数组的个数；
res += even;
完整遍历如下：
while (r < nums.size()) {
if (cnt < k && nums[r++] % 2 == 1) cnt ++;
if (cnt == k) {
even = 1;
while (!(nums[l++] % 2)) even ++;
cnt --;
}
res += even;
}
返回遍历结束后的累计值；
return res;
提交总览：
至此，双指针方法结束。
最后，来看一下前缀和的思路：
遍历原数组中每个位置 i ，如果 i 之前（包含自身） 1 的个数一共 odd 个（也就是前缀和），那么我们只需要看有多少个位置 j < i 满足 1 的前缀和等于 odd-k ，那么 [j + 1 , i] 就是正好包含 k 个 1 的子数组。
所以我们只需要用一个计数数组来记录一下前缀和对应的出现次数就行了，然后每次取出 odd-k 的次数加到答案里就行了。
代码实现：
含 1 的个数在 0 到 n 之间，所以要申请长度为 nums.size() + 1的数组；
vector<int> count(nums.size() + 1 , 0);
申请返回值和 1 的计数；
int res = 0;
int odd = 0;
因为 0 可以不选，这种存在，所以赋初值为 1 ；
count[0] = 1;
遍历数组，计数 odd 值对应的 count，如果 odd值大于等于 k ，开始累加；
for (int i = 0; i < nums.size(); i++) {
odd += nums[i] % 2;
if (odd >= k) res += count[odd - k];
count[odd] ++;
}
返回遍历结束后的累加结果；
return res;
提交总览：
至此，前缀和方法结束。
