题解 | 能量共振

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;

const int N = 1e6 + 10;

int n, res, cnt;
LL a[N];
map<LL,int> mp, mp2;

int main() {
    ios :: sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> n;
    mp[0] = 0;
    res = 2e6;
    for(int i=1; i<=n; i++) {
        cin >> a[i];
        a[i] += a[i - 1];
        if(mp.count(a[i])) {
            int t1 = mp[a[i]];
            mp2[i] = t1;
            if(mp2.count(t1)) {
                int t2 = mp2[t1];
                if(i - t2 < res) {
                    res = i - t2;
                    cnt = 1;
                } else if(i - t2 == res) {
                    cnt ++;
                }
            }
        }
        mp[a[i]] = i;
    }
    if(cnt) cout << res << ' ' << cnt;
    else cout << "-1 -1";

    return 0;
}

贪心地从前往后遍历时找每个点最近的区间和为0的点，可以用哈希表，然后再找使那个点区间和也为0的最近的点，两个区间合并更新答案。不用找所有的使其和为0的点，只用找离的最近的即可，可以看出来如果存在一个非最近的点使满足条件，那么一定可以转化成与其最近的一点结合从而得到更优的答案。