周赛 354
T1. 特殊元素平方和（Easy）
- 标签：模拟、数学
T2. 数组的最大美丽值（Medium）
- 标签：排序、二分查找、同向双指针
T3. 合法分割的最小下标（Medium）
- 标签：数学、前后缀分解
T4. 最长合法子字符串的长度（Hard）
- 标签：同向双指针
T1. 特殊元素平方和（Easy）
https://leetcode.cn/problems/sum-of-squares-of-special-elements/
题解一（模拟）
简单模拟题，枚举每个下标检查是否能被 n 整除，同时记录结果。
class Solution {
public:
int sumOfSquares(vector<int>& nums) {
int ret = 0;
int n = nums.size();
for (int i = 0; i < nums.size(); i++) {
if (n % (i + 1) == 0) ret += nums[i] * nums[i];
}
return ret;
}
};
复杂度分析：
- 时间复杂度：$O(n)$
- 空间复杂度：$O(1)$
题解二（模拟 + 优化）
事实上，当下标 i 可以被 n 整除时，那么有下标 n / i 也可以被 n 整除，因此我们只需要检查 [0, \sqrt(n)] 的范围。
- 1、将 nums[0] 和 nums[n - 1] 的平方值添加到结果中（如果数组长度不大于 1，则不需要添加 nums[n - 1] 的影响）；
- 2、从 2 到 sqrt(n) 的范围内遍历所有元素下标 i，如果 n 能够被 i 整除，那么我们将 nums[i-1] 的平方值和 nums[n/i-1] 的平方值分别添加到结果中（如果 i 和 n/i 相等，我们只添加其中一个值，以避免重复）；
class Solution {
public:
int sumOfSquares(vector<int>& nums) {
int ret = nums[0] * nums[0];
int n = nums.size();
if (n < 2) return ret;
ret += nums[n - 1] * nums[n - 1];
for (int i = 2; i <= sqrt(n); i++) {
if (n % i != 0) continue;
ret += nums[i - 1] * nums[i - 1];
if (i != n / i) {
ret += nums[n / i - 1] * nums[n / i - 1];
}
}
return ret;
}
};
复杂度分析：
- 时间复杂度：$O(\sqrt(n))$
- 空间复杂度：$O(1)$
其他语言解法见 LeetCode 题解页：枚举优化的 O(sqrt(n) 时间解法（C++/Python/Kotlin）
T2. 数组的最大美丽值（Medium）
https://leetcode.cn/problems/maximum-beauty-of-an-array-after-applying-operation/
题解一（排序 + 二分查找）
根据题目操作描述，每个元素都可以修改为范围在 [nums[i] - k, nums[i] + k] 之间的任意元素，我们把两个元素的差视为元素的相似度，那么差值小于 2*k 的两个数就能够转换为相等数（增大较小数，同时减小较大数）。
由于美丽值和数组顺序无关，我们先对数组排序，然后枚举元素作为左值，再寻找最远可匹配的右值（nums[i] + 2 * k），可以使用二分查找寻找不大于右值的最大元素。
class Solution {
public:
int maximumBeauty(vector<int>& nums, int k) {
sort(nums.begin(), nums.end());
int ret = 0;
for (int i = 0; i < nums.size(); i++) {
int left = i;
int right = nums.size() - 1;
while (left < right) {
int mid = (left + right + 1) / 2;
if (nums[mid] > nums[i] + 2 * k) {
right = mid - 1;
} else {
left = mid;
}
}
ret = max(ret, left - i + 1);
}
return ret;
}
};
复杂度分析：
- 时间复杂度：$O(nlgn)$ 瓶颈在排序，模拟时间为 $O(nlgn)$；
- 空间复杂度：$O(lgn)$ 瓶颈在排序。
题解二（排序 + 同向双指针）
根据题目操作描述，每个元素都可以修改为范围在 [nums[i] - k, nums[i] + k] 之间的任意元素，我们把这个范围视为一个可选区间。那么问题的最大美丽值正好就是所有区间的最多重叠数，这就是经典的 leetcode 253. 会议室 II 问题
由于区间重叠数和顺序无关，我们可以对所有元素排序（由于区间长度相等，等价于按照结束时间排序），使用同向双指针求解：
- 维护重叠区间的左右指针 i 和 j
- 如果当前区间 [j] 与左指针指向的区间不重叠，则将左指针 i 向右移动，并记录最大重叠数
class Solution {
public:
int maximumBeauty(vector<int>& nums, int k) {
sort(nums.begin(), nums.end());
int i = 0;
int ret = 0;
for (int j = 0; j < nums.size(); j++) {
while (nums[j] - k > nums[i] + k) i++;
ret = max(ret, j - i + 1);
}
return ret;
}
};
复杂度分析：
- 时间复杂度：$O(nlgn)$ 瓶颈在排序，同向双指针模拟时间为 $O(n)$；
- 空间复杂度：$O(lgn)$ 瓶颈在排序。
其他语言解法见 LeetCode 题解页：会议室问题求最大重叠区间数、同向双指针（C++/Python/Kotlin/TypeScript）
T3. 合法分割的最小下标（Medium）
https://leetcode.cn/problems/minimum-index-of-a-valid-split/
题解一（数学 + 前后缀分解）
根据题目描述，支配元素是指数组中的众数，同时要求出现次数严格大于数组一半长度，所以支配元素可能是 -1。其实，支配元素的定义与经典题目 169. 多数元素 和 剑指 Offer 39. 数组中出现次数超过一半的数字 定义是相同的。
容易证明，无论数组如何分割，子数组的支配元素要么不存在，要么就等于原数组的支配元素：
- 假设 cnt1 是左子数组的支配元素，cnt2 是右子数组的支配元素，那么右 cnt1 * 2 > len1 且 cnt2 * 2 > len2；
- 由于两个子数组的支配元素相同，且满足两式相加右 (cnt1 + cnt2) * 2 > (len1 + len2)，说明子数组的支配元素与原数组相同。
因此，我们的算法是：
- 计算原数组的支配元素
- 并从左到右枚举分割点，并记录支配元素在左右子数组中的个数，当左右子数组中支配元素的数量条件成立时，返回下标。
class Solution {
public:
int minimumIndex(vector<int>& nums) {
// 计算支配元素
unordered_map<int, int> cnts;
int x = -1;
for (int i = 0; i < nums.size(); i++) {
++cnts[nums[i]];
if (x == -1 || cnts[nums[i]] > cnts[x]) {
x = nums[i];
}
}
// 枚举分割点
int leftXCnt = 0;
for (int i = 0; i < nums.size(); i++) {
if (nums[i] != x) continue;
leftXCnt++;
if (leftXCnt * 2 > i + 1 && (cnts[x] - leftXCnt) * 2 > nums.size() - 1 - i) return i;
}
return -1;
}
};
复杂度分析：
- 时间复杂度：$O(n)$ 求支配元素和枚举分割点的时间复杂度都是 $O(n)$；
- 空间复杂度：$O(n)$ 散列表空间。
题解二（摩尔投票优化）
题解一中使用散列表求原数组的支配元素，可以使用摩尔投票算法来优化空间复杂度：
- 我们将众数的权重视为 +1，把其他数视为 -1。
- 首先我们维护一个候选数 ，然后遍历数组的每个元素，如果 count == 0，说明它在当前的权重最大，那么将它记为 candidate，对于接下来的元素，如果它等于 candidate，则 count ++，否则 count--。
- 最终得到的 candidate 就是众数。
class Solution {
public:
int minimumIndex(vector<int>& nums) {
// 计算支配数
int x = -1;
int count = 0;
for (int i = 0; i < nums.size(); i++) {
if (0 == count) x = nums[i];
if (nums[i] == x) count++; else count --;
}
// 计算支配数出现次数
int total = 0;
for (int i = 0; i < nums.size(); i++) {
if (nums[i] == x) total ++;
}
// 枚举分割点
int leftXCnt = 0;
for (int i = 0; i < nums.size(); i++) {
if (nums[i] != x) continue;
leftXCnt++;
if (leftXCnt * 2 > i + 1 && (total - leftXCnt) * 2 > nums.size() - 1 - i) return i;
}
return -1;
}
};
复杂度分析：
- 时间复杂度：$O(n)$ 求支配元素和枚举分割点的时间复杂度都是 $O(n)$；
- 空间复杂度：$O(1)$ 仅使用常量级别空间。
其他语言解法见 LeetCode 题解页：数学、前后缀分解、摩尔投票 O(1) 空间（C++/Python/Kotlin）
T4. 最长合法子字符串的长度（Hard）
https://leetcode.cn/problems/length-of-the-longest-valid-substring/
题解一（暴力枚举子串· 超出时间限制）
这道题中 forbidden[i] 字符串的长度不超过 10，说明检查字符串匹配的时间常数是比较低的，我们先考虑暴力的解法。
- 使用同向双指针 i 和 j 枚举子串，并检查该子串是否合法；
- 由于在内存循环中移动 j 指针只是在 [i, j - 1] 的基础上增加字符 nums[j]，所以在检查的时候仅需要检查 [i, j] 范围中，以 nums[j] 为结尾的子字符串是否被禁用。同时，由于 forbidden[i] 的最大长度为 10，所以在检查时只需要检查长度不超过 10 的子串。
class Solution {
fun longestValidSubstring(word: String, forbidden: List<String>): Int {
val forbiddenSet = forbidden.toHashSet()
var ret = 0
for (i in 0 until word.length) {
for (j in i until word.length) {
if (!check(forbiddenSet, word, i, j)) break // 后续子串不可能合法
ret = Math.max(ret, j - i + 1)
}
}
return ret
}
// return：是否合法
private fun check(set: Set<String>, word: String, i: Int, j: Int): Boolean {
// 检查 [i,j] 中以新增字母 nums[j] 为右端点的所有子串方案是否被禁用
for (k in j downTo i) {
val key = word.substring(k, j + 1)
if (set.contains(key)) return false
}
return true
}
}
复杂度分析：
- 时间复杂度：$O(L + n2)$ 构造 $forbiddenSet$ 散列表的时间复杂度为 $O(L)$，其中 L 为 forbidden 中所有字符的总长度。枚举子串的个数为 $n^2$，而检查子串是否合法的时间复杂度是 $O(M^2)$，其中 n 是 word 字符串的长度，而 M 是子串的最大长度，M = 10，因此枚举阶段的时间复杂度是 $O(n2)$。
- 空间复杂度：$O(L)$ 散列表空间。
提示：我们可以使用滚动哈希优化 check 的时间复杂度到 O(M)，但由于 M 本身很小，优化效果不高。
题解二（同向双指针）
这道题需要结合 KMP 思想。
题解一中的 check 会重复计算多次子串，需要想办法剪枝：
- 由于我们是求最长子串，所以 [i + 1, j] 的结果不会由于 [i, j] 的结果。这说明了，如果 [i, j] 中存在不合法的子串，那么移动 i 指针 + 1 后再去重新枚举 j 指针，不可能获得更优解，完全没有必要枚举 i 指针，只需要在 [i, j] 不合法的时候移动 i 指针 + 1；
- 同时，在 check 函数中最早出现的非法子串位置，可以加快收缩 i 指针，直接将 i 指针指向最早出现的非法子串位置 + 1。
class Solution {
fun longestValidSubstring(word: String, forbidden: List<String>): Int {
// word = "leetcode", forbidden = ["de","le","e"]
val forbiddenSet = forbidden.toHashSet()
var ret = 0
var i = 0
for (j in 0 until word.length) {
// 不合法
while (true) {
val pivot = check(forbiddenSet, word, i, j)
if (-1 != pivot) i = pivot + 1 else break
}
ret = Math.max(ret, j - i + 1)
}
return ret
}
// return：最早的非法子串的起始位置
private fun check(set: Set<String>, word: String, i: Int, j: Int): Int {
// 检查 [i,j] 中以新增字母 nums[j] 为右端点的所有子串方案是否被禁用
for (k in Math.max(i, j - 10) .. j) {
val key = word.substring(k, j + 1)
if (set.contains(key)) return k
}
return -1
}
}
复杂度分析：
- 时间复杂度：$O(L + n·M^2)$ check 函数最多仅调用 n 次；
- 空间复杂度：$O(L)$ 散列表空间。