Leetcode -696.计数二进制字串
题目：给定一个字符串 s，统计并返回具有相同数量 0 和 1 的非空（连续）子字符串的数量，并且这些子字符串中的所有 0 和所有 1 都是成组连续的。
重复出现（不同位置）的子串也要统计它们出现的次数。
示例 1：
输入：s = “00110011”
输出：6
解释：6 个子串满足具有相同数量的连续 1 和 0 ：“0011”、“01”、“1100”、“10”、“0011” 和 “01” 。
注意，一些重复出现的子串（不同位置）要统计它们出现的次数。
另外，“00110011” 不是有效的子串，因为所有的 0（还有 1 ）没有组合在一起。
示例 2：
输入：s = “10101”
输出：4
解释：有 4 个子串：“10”、“01”、“10”、“01” ，具有相同数量的连续 1 和 0 。
提示：
1 <= s.length <= 10^5
s[i] 为 ‘0’ 或 ‘1’
思路是遍历字符串，前一个与后一个字符相同的时候，就用 curr 记录这个字符有几个相同；如果当前字符与后一个字符不相同，那么它们必定是符合题意的子字符串，用 ans 统计符合题意的子符串的数量，同时把 curr 赋给 prev；每次出现相同的字符的时候都要和 prev 比较，如果 prev 大于等于 curr，就说明是符合题意的子字符串；
int countBinarySubstrings(char* s) { int curr = 1, prev = 0, ans = 0; //遍历字符串，例如字符串"00110011" //如果相邻的两个字符相同，如上面的 0 和 0 相同，curr就纪录 0 出现了两次 //继续遍历，判断第二位与第三位，它们不相同，就将 curr 赋给 prev ，curr 置为1，然后判断prev是否大于等于curr，如果是，ans就++；此时是记录第二位和第三位这个 01 的子串 //只要它们相邻两位不相同的，就必定是符合题意的子串，prev 也必定大于等于curr，curr是记录上一次0或者1连续的个数 //接下来遍历到第三位，判断第三位和第四位，都是1，相同curr就记录 1 出现了两次，注意此时 prev 是2，prev是记录上一次 0 出现的次数，此时prev等于curr，ans也++；此时是记录 0011 这个字串 //后面以此类推 for (int i = 0; i < strlen(s) - 1; i++) { if (s[i] == s[i + 1]) { curr++; } else { prev = curr; curr = 1; } if (prev >= curr) { ans++; } } return ans; }
Leetcode -697.数组的度
题目：给定一个非空且只包含非负数的整数数组 nums，数组的度的定义是指数组里任一元素出现频数的最大值。
你的任务是在 nums 中找到与 nums 拥有相同大小的度的最短连续子数组，返回其长度。
示例 1：
输入：nums = [1, 2, 2, 3, 1]
输出：2
解释：
输入数组的度是 2 ，因为元素 1 和 2 的出现频数最大，均为 2 。
连续子数组里面拥有相同度的有如下所示：
[1, 2, 2, 3, 1], [1, 2, 2, 3], [2, 2, 3, 1], [1, 2, 2], [2, 2, 3], [2, 2]
最短连续子数组[2, 2] 的长度为 2 ，所以返回 2 。
示例 2：
输入：nums = [1, 2, 2, 3, 1, 4, 2]
输出：6
解释：
数组的度是 3 ，因为元素 2 重复出现 3 次。
所以[2, 2, 3, 1, 4, 2] 是最短子数组，因此返回 6 。
提示：
nums.length 在 1 到 50, 000 范围内。
nums[i] 是一个在 0 到 49, 999 范围内的整数。
思路是先算出这个数组的度，再使用双指针遍历这个数组，这两个指针维护符合数组的度的子数组，再进行数组收缩，找到最短连续子数组；
int findShortestSubArray(int* nums, int numsSize) { //定义一个hash数组并初始化为0 int hash[50000] = { 0 }; //maxtimes记录这个数组的度 int maxtimes = 0; for (int i = 0; i < numsSize; i++) { maxtimes = fmax(maxtimes, ++hash[nums[i]]); } //重新将hash数组初始化为0 memset(hash, 0, sizeof(hash)); //下标 left 和 right 都从0开始，这两个指针维护一段数组，这段数组的度等于整个数组的度 //ans 是返回的最短连续子数组的元素个数，初始化成数组长度 int left = 0, right = 0, ans = numsSize; for (right = 0; right < numsSize; right++) { //统计nums[right]这个数出现了几次 hash[nums[right]]++; //当这个数组的度等于这个数出现的次数的时候，ans取ans和这两个指针之间的长度的较小值 //例如[1,2,2,3,1]这个数组，当 right 遍历到第二个2的时候，left 还在第一个1这里，此时 right - left + 1 为3，还不是最短连续子数组的元素个数 //所以要让 left 向 right 靠近，因此 nums[left] 出现的次数自减，left++；nums[left] 出现的次数自减的原因是，如果不自减会出现死循环，就不能判断后面的元素了 while (maxtimes == hash[nums[right]]) { ans = fmin(ans, right - left + 1); hash[nums[left]]--; left++; } } return ans; }
