特殊元素平方和

如果 数组的长度n 能够被 i 整除，即 n % i == 0 ，则认为 num[i] 是一个 特殊元素 ，求所有特殊元素的平方的和

这当然是无脑模拟T1就ok

  class Solution {
  public:
      int sumOfSquares(vector &nums) {
          int ans = 0, n = nums.size();
          for (int i = 0; i < nums.size(); i++)
              if (n % (i + 1) == 0) ans += nums[i] * nums[i];
          return ans;
      }
  };

数组的最大美丽值

对于数组的每个元素$x$都可以被修改为$[x-k,x+k]$的任意一个数，此时我们根据$0<=nums[i]<=10^5$可以知道如果修改为负数，或者修改为大于$10^5$的过程和修改为0和$10^5$的区间是有重叠的，所以最大值一定在端点可知。

由此我们只需要求$[0,10^5]$的数字，每个数字有多少个被修改成的可能。

每个数对他修改区间每个区间$[x-k,x+k]$的贡献度都为1，因此我们可以采用差分的方法得到这个最大值。

  class Solution {
  public:
      int f[100010];

      int maximumBeauty(vector &nums, int k) {
          for (auto &x: nums) {
              f[max(0, x - k)]++;
              f[min(100000, x + k) + 1]--;
          }
          int cnt = 0, ans = 0;
          for (int i = 0; i <= 100000; i++) {
              cnt += f[i];
              ans = max(ans, cnt);
          }
          return ans;
      }
  };

合法分割的最小下标

分割为两个合法区间，保证两个区间超过一半以上次数的值的频率大于区间长度的一半，求最小的分割下标。

对此可以先计算出每个数的情况，先计算出所有数的频率，作为第一次循环，

第二次循环，得到前面区间的频率和后面剩余的频率，只要通过哈希表验证前后区间的值是否成立即可。

关键点：前后两个区间的支配元素一致的情况下。且一定是前一个区间刚加入（后一个区间删除的）的数字

哈希表模拟，不考虑哈希查找的复杂度，整体复杂度$O(n)$

class Solution {
public:
    int minimumIndex(vector<int> &nums) {
        map<int, int> all, cnt;
        for (auto &x: nums) all[x]++;
        int n = nums.size();
        for (int i = 0; i < n; i++) {
            all[nums[i]]--;
            cnt[nums[i]]++;
            if (cnt[nums[i]] * 2 > i + 1) 
                if (all[nums[i]] * 2 > (n - (i + 1))) return i;
        }
        return -1;
    }
};

最长合法子字符串的长度

给定一个字符串s和一个字符串数组f，求最长的s不包含f内任意字符串的数组的长度

当我们使用滑动窗口方法解决这个问题时，我们维护了两个指针：l 和 r。初始时，l 和 r 都指向字符串的开头。

我们通过不断移动 r 指针来扩大窗口。在每个位置，我们检查窗口中的子字符串是否有效。如果子字符串出现在 forbidden 数组中，我们就需要更新 l 指针，并缩小窗口的大小。

具体来说，在每个 r 的位置，我们从 r 到 l 的范围内向后遍历，检查子字符串是否在 forbidden 数组中。如果找到了一个子字符串在 forbidden 数组中，我们就将 l 移动到它的后一个位置，并更新窗口的大小。

class Solution {
public:
    int longestValidSubstring(string word, vector<string>& forbidden) {
        set<string> h(forbidden.begin(), forbidden.end());
        int n = word.size(), ans = 0, l = 0;
        for (int r = 0; r < n; r++) {
            for (int i = r; i >= l; i--) {
                if (r - i >= 10) break;
                if (h.count(word.substr(i, r - i + 1))) {
                    l = i + 1;
                    break;
                }
            }
            ans = max(ans, r - l + 1);
        }
        return ans;
    }
};