解题思路

已知一个长度为 N 的整数数组 A（有正有负），我们要在其中找若干子数组，使得：

• 这个子数组可以被分成左右两个连续的非空子数组；
• 左右两个子数组的元素和都为 0；
• 在所有满足条件的子数组里，找出“长度最长”的长度 L，并统计长度为 L 的这类子数组有多少个；
• 若不存在这样的子数组，则输出 -1 -1。

把子数组区间写成 [l, r]，中间分割点为 k（左闭右闭）：

• 左段：[l, k]，右段：[k+1, r]
• 要求：sum(l..k) = 0 且 sum(k+1..r) = 0

前缀和 + 分组

设前缀和数组 pre[i] 表示前 i 个元素之和（pre[0] = 0，pre[i] = a[0]+...+a[i-1]），则

• sum(l..k) = pre[k+1] - pre[l]
• sum(k+1..r) = pre[r+1] - pre[k+1]

要两段都为 0，即

• pre[k+1] = pre[l]
• pre[r+1] = pre[k+1]

所以有：pre[l] = pre[k+1] = pre[r+1]，并且下标满足 l < k+1 < r+1，也就是一组三个严格递增的前缀和下标，且值相同。

因此： 一个满足条件的子数组 [l, r] 等价于存在一个前缀和值 v，在它的所有出现位置中有三个下标 i < j < t，使得

• i = l
• t = r+1
• pre[i] = pre[j] = pre[t] = v
• 子数组长度 len = r - l + 1 = t - i

于是我们只需要在前缀和中，按“值”把所有下标分组，然后在每一组中寻找三元组即可。

第一步：求全局最大长度

对前缀和中某个值 v，假设它出现的位置为有序数组

P = [p0, p1, ..., p(m-1)]（已按下标从小到大）

只要 m >= 3，就必然存在满足条件的子数组，并且：

• 对这个值 v 的所有合法子数组中，长度最长的一定是使用最左和最右两个下标：[p0, p(m-1) - 1]
• 其长度为 len_v_max = p(m-1) - p0

原因：任意合法子数组由一对 (pi, pj)（j >= i+2）决定，长度 pj - pi，最大差值显然就是最左和最右的差。

因此：

1. 计算所有前缀和，把每个位置下标加入到 map[pre] 的向量里；
2. 对于每个 pre 值的向量 P，若 len(P) >= 3，计算 P.back() - P.front()；
3. 所有这样的值中取最大值，记为 maxLen；若始终没有 len(P) >= 3，则答案为 -1 -1。

第二步：统计最大长度的子数组个数

现在 maxLen 已知，对每种前缀和值 v 及其位置数组 P，需要统计满足：

• pj - pi = maxLen
• j >= i + 2（保证中间存在至少一个下标）

的有序对 (i, j) 的个数。

注意到 P 是升序的，因此可以用 双指针 在线性时间内完成统计：

• 固定右指针 j 从左到右遍历；

• 左指针 i 也从左往右移动，并保持：

  • 当 pj - pi > maxLen 时，向右移动 i，直到 pj - pi <= maxLen；

• 对于当前 j，若 j >= i+2 且 pj - pi == maxLen，那么存在且只存在这一对 (i, j) 符合条件（因为 P 严格递增，差值为 maxLen 的 i 只有一个），于是总答案加一。

对所有 v 的位置数组做一次双指针，整体还是线性级别。

复杂度分析

设数组长度为 N：

• 计算前缀和并建表：O(N)
• 第一遍扫描所有分组求最大长度：总元素数为 N+1，为 O(N)
• 第二遍双指针统计个数：同样是对所有前缀位置做线性扫描，为 O(N)

总时间复杂度：O(N) 总空间复杂度：O(N)（存储前缀和分组的下标）

在 N <= 10^6 的范围内可以通过。

代码实现

Python

import sys
from collections import defaultdict

# 功能函数：根据数组 a 计算最长长度和个数
def solve(a):
    n = len(a)
    mp = defaultdict(list)  # key: 前缀和, value: 该前缀和出现的所有下标
    prefix = 0
    mp[prefix].append(0)  # pre[0] = 0，对应下标 0

    # 构建前缀和分组
    for i in range(1, n + 1):
        prefix += a[i - 1]
        mp[prefix].append(i)

    # 第一次遍历：找出最大长度
    max_len = -1
    for positions in mp.values():
        m = len(positions)
        if m >= 3:
            cur_len = positions[-1] - positions[0]
            if cur_len > max_len:
                max_len = cur_len

    # 如果不存在满足条件的子数组
    if max_len < 0:
        return -1, -1

    # 第二次遍历：统计长度为 max_len 的子数组个数
    count = 0
    for positions in mp.values():
        m = len(positions)
        if m < 3:
            continue
        i = 0  # 左指针
        for j in range(m):  # 右指针
            # 保证差值不超过 max_len
            while i + 2 <= j and positions[j] - positions[i] > max_len:
                i += 1
            # j 至少比 i 大 2，才能保证中间有元素
            if j >= i + 2 and positions[j] - positions[i] == max_len:
                count += 1

    return max_len, count


def main():
    data = sys.stdin.read().strip().split()
    if not data:
        return
    n = int(data[0])
    a = list(map(int, data[1:1 + n]))

    max_len, count = solve(a)
    print(max_len, count)


if __name__ == "__main__":
    main()

Java

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

/**
 * ACM 风格主类
 */
public class Main {

    // 功能函数：根据数组 a 计算最长长度和个数
    private static long[] solve(int[] a) {
        int n = a.length;

        // 使用 HashMap<Long, ArrayList<Integer>> 存储每个前缀和的所有下标
        HashMap<Long, ArrayList<Integer>> map = new HashMap<>();
        long prefix = 0L;

        ArrayList<Integer> list0 = new ArrayList<>();
        list0.add(0);
        map.put(prefix, list0); // 前缀和 0 在下标 0 出现

        for (int i = 1; i <= n; i++) {
            prefix += a[i - 1];
            ArrayList<Integer> pos = map.get(prefix);
            if (pos == null) {
                pos = new ArrayList<>();
                map.put(prefix, pos);
            }
            pos.add(i);
        }

        long maxLen = -1;

        // 第一次遍历：求最大长度
        for (ArrayList<Integer> pos : map.values()) {
            int m = pos.size();
            if (m >= 3) {
                long curLen = (long) pos.get(m - 1) - (long) pos.get(0);
                if (curLen > maxLen) {
                    maxLen = curLen;
                }
            }
        }

        if (maxLen < 0) {
            return new long[]{-1, -1};
        }

        long count = 0;

        // 第二次遍历：用双指针统计长度为 maxLen 的个数
        for (ArrayList<Integer> pos : map.values()) {
            int m = pos.size();
            if (m < 3) {
                continue;
            }
            int i = 0; // 左指针
            for (int j = 0; j < m; j++) { // 右指针
                // 控制差值不超过 maxLen
                while (i + 2 <= j &&
                        (long) pos.get(j) - (long) pos.get(i) > maxLen) {
                    i++;
                }
                // j 至少比 i 大 2，且差值等于 maxLen
                if (j >= i + 2 &&
                        (long) pos.get(j) - (long) pos.get(i) == maxLen) {
                    count++;
                }
            }
        }

        return new long[]{maxLen, count};
    }

    // 快速输入类（根据数据范围使用）
    private static class FastScanner {
        private final InputStream in;
        private final byte[] buffer = new byte[1 << 16];
        private int ptr = 0, len = 0;

        FastScanner(InputStream is) {
            in = is;
        }

        private int read() throws IOException {
            if (ptr >= len) {
                len = in.read(buffer);
                ptr = 0;
                if (len <= 0) return -1;
            }
            return buffer[ptr++];
        }

        int nextInt() throws IOException {
            int c;
            do {
                c = read();
                if (c == -1) return -1;
            } while (c <= ' ');

            int sign = 1;
            if (c == '-') {
                sign = -1;
                c = read();
            }

            int val = 0;
            while (c > ' ') {
                val = val * 10 + (c - '0');
                c = read();
            }
            return val * sign;
        }
    }

    public static void main(String[] args) throws Exception {
        FastScanner fs = new FastScanner(System.in);

        int n = fs.nextInt();
        if (n == -1) {
            return;
        }
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = fs.nextInt();
        }

        long[] ans = solve(a);
        System.out.println(ans[0] + " " + ans[1]);
    }
}

C++

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

// 功能函数：根据数组 a 计算最长长度和个数
pair<long long, long long> solve(const vector<int> &a) {
    int n = (int)a.size();

    // 使用 unordered_map<long long, vector<int>> 存储每个前缀和的所有下标
    unordered_map<long long, vector<int>> mp;
    mp.reserve(n * 2);          // 预留空间，减少扩容
    mp.max_load_factor(0.7f);   // 降低装载因子，提高性能

    long long prefix = 0;
    mp[prefix].push_back(0);    // 前缀和 0 在下标 0 出现

    for (int i = 1; i <= n; ++i) {
        prefix += a[i - 1];
        mp[prefix].push_back(i);
    }

    long long maxLen = -1;

    // 第一次遍历：求最大长度
    for (auto &kv : mp) {
        const vector<int> &pos = kv.second;
        int m = (int)pos.size();
        if (m >= 3) {
            long long curLen = (long long)pos[m - 1] - (long long)pos[0];
            if (curLen > maxLen) {
                maxLen = curLen;
            }
        }
    }

    if (maxLen < 0) {
        return {-1, -1};
    }

    long long count = 0;

    // 第二次遍历：用双指针统计长度为 maxLen 的子数组个数
    for (auto &kv : mp) {
        const vector<int> &pos = kv.second;
        int m = (int)pos.size();
        if (m < 3) continue;

        int i = 0; // 左指针
        for (int j = 0; j < m; ++j) { // 右指针
            // 保证差值不超过 maxLen
            while (i + 2 <= j &&
                   (long long)pos[j] - (long long)pos[i] > maxLen) {
                ++i;
            }
            // 需要 j 至少比 i 大 2，并且差值等于 maxLen
            if (j >= i + 2 &&
                (long long)pos[j] - (long long)pos[i] == maxLen) {
                ++count;
            }
        }
    }

    return {maxLen, count};
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    if (!(cin >> n)) {
        return 0;
    }
    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }

    auto ans = solve(a);
    cout << ans.first << " " << ans.second << "\n";

    return 0;
}

题目内容

已知数组 $A$，数组 $A$ 内元素为带符号整数，希望在该数组内找到满足如下条件的子数组：

子数组可分为两个连续的子子数组，这两个子子数组长度可互不相同，但他们的元素和都为零

即满足对于子数组区间 $[i,j)$, 存在中同元素 $k(i<k<j)$, 使得 $\sum [i,k) == \sum [k,j)==0$ ；

希望你找出所有满足上述条件数组中的长度最短的子数组。

输入描述

输入由两行组成:第一行包含一个数字 $N$ ，代表数组的元素数量

第二行包含 $N$ 个数字 $X_i(0<=1<N)$，代表数组的元素内容

输入约束：

1.$1 <= N <= 10^6$

2.$-10000 <= X_i <= 10000$

输出描述

输出满足条件数组的最短长度 以及 该类数组的个数

如果不存在，分别输出 $-1$ 和 $-1$

样例1

输入

5
1 -1 1 -1 1

输出

4 2

说明

注意同一个元素是允许出现再多个不同的子数组中的

本例子中有两种子数组分割方法

方案 $1$ : $[1$ $-1] [1$ $-1]$ $1$

方案 $2$ : $1$ $[-1$ $1][-1$ $1]$

样例2

输入

7
0 100 1 300 2 10 0

输出

-1 -1

说明

找不到满足要求的子数组

样例3

输入

7
100 1 -1 3 -2 100

输出

5 -1

说明

子数组 {$1$ $-1$ $3$ $-2$ $-1$} 满足条件

其可分为两个满足条件的子子数组 {$1$ $-1$} 和 {$3$ $-2$ $-1$}