题解 | 能量共振

题意为找最短的共振区间的长度和个数，共振区间满足存在分割点，使区间被分为两个和为0的子区间

也就是说，如果存在两个连续子区间a1...ai，ai+1...aj，且这两个子区间和为0，那么就可以合并为1个共振区间

我们要最小化共振区间，就要最小化每个和为0的子区间的长度，一个经典的做法是使用前缀和和map映射

map记录前缀和为sum时最近的下标i，即prefix[i]=a1+a2+...ai=sum，我们遍历数组1-n,不断做前缀和,

可以得到prefix[j]=a1+a2+.....aj的值，当j>i时 如果prefix[j]=prefix[i]=sum 那么a[i+1]+a[i+2]+.....a[j]的和=prefix[j]-prefix[i]=0

我们就找到了区间和为0的子区间，并且可以证明，这个子区间一定是长度最小的，因为我们每次遍历数组时都更新了map[sum]的最近下标

我们有了每一段和为0的子区间，接下来就是把它们组装起来，并记录共振区间长度

一个很容易想到的贪心策略是,对每个和为0的子区间，我最多只跟另外一个子区间合并，这样得到的共振区间一定是最小的

因此我们可以用映射来记录子区间，map[i]=j表示存在(i,j）的和为0的子区间，最多跟一个子区间合并，那么我就检查map[j+1]是否存在 如果存在以j+1为开头的和为0的子区间，我就把这两个区间合并为共振区间，这一定是对i开头的和为0的子区间的最优合并方法，否则就没有区间给i开头的和为0的子区间合并了，我们跳过这个子区间。

最后遍历1-n 对每个以i开头的子区间求最小共振区间即可

时间复杂度(Onlogn)

#include <bits/stdc++.h>

using namespace std;
using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;
using u128 = unsigned __int128;
using i128 = __int128;
const int N = 2e6 + 10;

vector<i64> a(N);
map<i64, i64> mp, id;//id[i]=j表示存在(i,j)的区间和为0的子区间
int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int n;
    cin >> n;
    for (int i = 1; i <= n; ++i)
        cin >> a[i];
    i64 sum = 0;
    mp[0] = 0;
    for (int i = 1; i <= n; ++i)
    {
        sum += a[i];
        if (mp.count(sum))
        {
            id[mp[sum] + 1] = i;//记录区间
        }
        mp[sum] = i;
    }
    i64 cnt = 0, ans = 1e18;
    for (int i = 1; i <= n; ++i)
    {
        if (id[i] && id[id[i] + 1])
        {

            i64 len = id[id[i] + 1] - i + 1;
            if (len < ans)
            {
                ans = len;
                cnt = 1;
            }
            else if (len == ans)
                cnt++;
        }
    }
    if(cnt)
        cout << ans << ' ' << cnt << '\n';
    else
        cout << -1 << ' ' << -1 << '\n';
    return 0;
}