leetcode 周赛 473，排名 105

零、背景

这次比赛整体难度不高，其中两题可用“延迟前缀和”统一解决。
由于之前没系统用过这个技巧，中途思考了一会儿，最终排名 105。

PS：43 分钟做完比赛（11:13），写题解时还在 80 多名，写完后掉到 105 名。

A: 十进制
B: 贪心双指针
C: 延迟前缀和
D: 延迟前缀和

排名：105
代码地址： https://github.com/tiankonguse/leetcode-solutions

一、移除十进制表示中的所有零

题意：给一个十进制数字，问删除其中的所有 0 后，剩下的数字是多少。

思路：按位遍历

逐位获取当前数字，若不是 0 就加入答案。
由于遍历是从低位到高位，最后需要反转一下。
如果不想反转，就维护一个乘数 base，每次乘 10。

while (n) {
  int digit = n % 10;
  n /= 10;
  if (digit != 0) {
    ans = ans + digit * base;
    base *= 10;
  }
}

二、最大交替平方和

题意：给一个数组，可以重新排列，奇数位置的平方和减去偶数位置的平方和，问最大值是多少（位置按 1 开始计数）。

思路：贪心双指针

显然，最大的数放在奇数位置，最小的数放在偶数位置。
所以排序后，双指针分别从头和尾开始取数即可。

vector<ll> nums2;
nums2.reserve(n);
for (ll v : nums) {
  nums2.push_back(v * v);
}
sort(nums2.begin(), nums2.end());
int l = 0, r = n - 1;
while (l <= r) {
  ans += nums2[r--];
  if (l <= r) {
    ans -= nums2[l++];
  }
}

三、边界与内部和相等的稳定子数组

题意：给一个数组，问存在多少长度不小于 3 的子数组，左右边界都与内部和相等。

思路：延迟前缀和

数据范围是 1e5，显然不能暴力枚举。
故在枚举每一位的时候，需要找到前缀的一些特征，从而快速计算出当前位置为右边界的子数组个数。

假设存在这样的子数组，则大概这样：[a, b, ..., c, d]，其中 a 和 d 是边界，b, ..., c 是内部。
则有 a = d = b + ... + c，即 a = d = sum(b, ..., c)。

这里前缀和 prefixSum[i] 指“包含第 i 个元素”的前缀和，则有

prefixSum[ai] = prefixSum[di] - sum(b, ..., c) - d 
              = prefixSum[di] - 2 * d 

故可以维护一个“前缀和与最后一个元素”的二元组哈希计数表，从而快速找到满足条件的子数组个数。

问题：如果连续元素都是 0，会计算到长度小于 3 的子数组。
例如 [0, 0, 0]，会被计算为 3 个子数组，但实际上只有 1 个。

还是看上面的等式 [a, b, ..., c, d]。
需要保证 b, ..., c 不为空，即中间至少有一个元素。
我们期望在前缀 prefixSum[ci] 之前找到所有的匹配的答案。

但是目前我们把 prefixSum[ci] 也加入到了哈希表中，导致匹配上了。
所以我们需要延迟把 prefixSum[ci] 加入到哈希表中。

ll sum = 0;
ll ans = 0;
map<pair<ll, ll>, int> mp;
for (int i = 0; i < n; i++) {
  const ll v = nums[i];
  sum += v; // prefixSum[i]：包含第 i 个元素
  const pair<ll, ll> p = {sum - 2 * v, v};
  if (i >= 2 && mp.count(p)) { // 保证子数组长度 >= 3
    ans += mp[p];
  }
  if (i > 0) {
    mp[{sum - v, nums[i - 1]}]++; // 延迟把上一个加入
  }
}

四、统计有序数组中可被 K 整除的子数组数量

题意：给一个非降序数组，问有多少不同子数组的和能被 K 整除。
不同子数组定义：如果子数组的值序列不同，则认为是不同子数组。

思路：延迟前缀和 + 同值段去重

首先分析没有不同子数组的情况。
显然是标准的前缀和取模问题。

ll sum = 0;
ll ans = 0;
unordered_map<ll, ll> count;
count[0] = 1;
for (ll v : nums) {
  sum += v;
  const ll mod = sum % k;
  if (count.count(mod)) {
    ans += count[mod];
  }
  count[mod]++;
}

接下来分析什么情况下两个子数组会相同。

题目已经强调了数组是非降序的。
如果这两个子数组包含多个不同的元素，不妨只看两个不同元素，且长度相等，且首尾元素相等。
例如 [2, 2, 3, 3] 和 [2, 3, 3, 3]。
显然，这两个子数组的和不可能相等，因为第一个元素变化为第二个元素的位置不同，即每个元素的个数不同。

由此可以得出结论：如果两个子数组相同，则这两个子数组不仅长度相同，而且所有元素都是相同的（即“整段同值”）。

那怎么避免重复计算呢？
由于数组是非降序的，所以相同元素必然是连续出现的。

对于固定长度的第一个相同元素子数组，可以从前缀和中计算答案。
为了避免后续相同长度的子数组重复统计，应“延迟”把这一段内的前缀加入计数。

这不就和上一题完全一样了吗？
先对相同元素进行分组，然后在每一组内进行延迟前缀和计算即可。

vector<pair<ll, ll>> nums; // 预处理出 (value, count)
ll sum = 0;
ll ans = 0;
unordered_map<ll, ll> count;
count[0] = 1;
for (auto& [v, cnt] : nums) {
  ll sum0 = sum;  // 不包含 v 的前缀和
  for (ll i = 1; i <= cnt; i++) {
    sum0 += v;
    if (count.count(sum0 % k)) {
      ans += count[sum0 % k];
    }
  }
  // 第二步：延迟更新计数器
  for (ll i = 1; i <= cnt; i++) {
    sum += v;
    count[sum % k]++;
  }
}

五、最后

这次比赛的主要收获是“延迟前缀和”这一技巧：

• 明确前缀和的定义（是否包含当前元素值组成二元组），推导与代码需一致；
• 按需“延迟”把当前元素/当前段的信息放入计数，规避重复匹配；
• 针对有序数组，结合同值段做去重（如“全相等序列”的唯一性）；

总体来看，后两题思路高度相似，基本是同一技巧的两种落地。

《完》

-EOF-

本文公众号：天空的代码世界
个人微信号： tiankonguse
公众号 ID： tiankonguse-code