能量共振

题目分析

给定一个长度为 $n$ 的整数数组，找到最短的子数组，使得该子数组可以被分成连续的两段，每段的元素之和都恰好为 $0$ 。输出最短长度和对应的子数组个数，若不存在则输出 -1 -1。

思路

前缀和 + 哈希分组

关键观察：如果子数组 $[i, j]$ 能在位置 $k$ 处被分成两段零和子数组，即 $\text{sum}(i, k) = 0$ 且 $\text{sum}(k+1, j) = 0$ ，那么用前缀和 $\text{pre}$ 来表示就是：

$ $\text{pre}[k] - \text{pre}[i-1] = 0 \quad \text{且} \quad \text{pre}[j] - \text{pre}[k] = 0$ $

也就是说 $\text{pre}[i-1] = \text{pre}[k] = \text{pre}[j]$ 。

问题转化：在前缀和数组中，找到三个下标 $p < q < r$ ，使得 $\text{pre}[p] = \text{pre}[q] = \text{pre}[r]$ ，对应的子数组长度为 $r - p$ ，我们要最小化这个长度。

具体做法：

计算前缀和数组 $\text{pre}[0..n]$ ，其中 $\text{pre}[0] = 0$ 。
将所有下标按前缀和的值分组（用哈希表）。
对于每个组内的下标列表（已天然有序），枚举所有相邻三元组 $(indices[i], indices[i+1], indices[i+2])$ ，计算跨度 $indices[i+2] - indices[i]$ 。
取全局最小跨度即为答案长度，同时统计个数。

为什么只需看相邻三元组？因为对于固定的首尾 $p$ 和 $r$ ，中间的 $q$ 只要存在一个即可。而要让 $r - p$ 最小，最优的 $p$ 和 $r$ 一定出现在排序后的相邻位置附近。更准确地说，对于任何跨度为 $r - p$ 的三元组 $(p, q, r)$ ，相邻三元组 $(indices[i], indices[i+1], indices[i+2])$ 的跨度不会更大，因此只检查相邻三元组即可。

代码

C++
Java

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

int main() {
    int n;
    scanf("%d", &n);
    vector<long long> pre(n + 1);
    pre[0] = 0;
    for (int i = 1; i <= n; i++) {
        long long x;
        scanf("%lld", &x);
        pre[i] = pre[i - 1] + x;
    }
    // 按前缀和的值分组，记录出现的下标
    unordered_map<long long, vector<int>> mp;
    for (int i = 0; i <= n; i++) {
        mp[pre[i]].push_back(i);
    }
    int minLen = INT_MAX;
    int cnt = 0;
    for (auto& [val, indices] : mp) {
        if (indices.size() < 3) continue;
        for (int i = 0; i + 2 < (int)indices.size(); i++) {
            int span = indices[i + 2] - indices[i];
            if (span < minLen) {
                minLen = span;
                cnt = 1;
            } else if (span == minLen) {
                cnt++;
            }
        }
    }
    if (minLen == INT_MAX) {
        printf("-1 -1\n");
    } else {
        printf("%d %d\n", minLen, cnt);
    }
    return 0;
}

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine().trim());
        StringTokenizer st = new StringTokenizer(br.readLine().trim());
        long[] pre = new long[n + 1];
        pre[0] = 0;
        for (int i = 1; i <= n; i++) {
            pre[i] = pre[i - 1] + Long.parseLong(st.nextToken());
        }
        HashMap<Long, List<Integer>> mp = new HashMap<>();
        for (int i = 0; i <= n; i++) {
            mp.computeIfAbsent(pre[i], k -> new ArrayList<>()).add(i);
        }
        int minLen = Integer.MAX_VALUE;
        int cnt = 0;
        for (List<Integer> indices : mp.values()) {
            if (indices.size() < 3) continue;
            for (int i = 0; i + 2 < indices.size(); i++) {
                int span = indices.get(i + 2) - indices.get(i);
                if (span < minLen) {
                    minLen = span;
                    cnt = 1;
                } else if (span == minLen) {
                    cnt++;
                }
            }
        }
        if (minLen == Integer.MAX_VALUE) {
            System.out.println("-1 -1");
        } else {
            System.out.println(minLen + " " + cnt);
        }
    }
}

复杂度分析

时间复杂度： $O(n)$ 。计算前缀和、哈希分组、遍历相邻三元组，每步都是线性的。
空间复杂度： $O(n)$ 。前缀和数组和哈希表各占 $O(n)$ 空间。