题解 | #能量共振#

题目链接

题目描述

在一项对时空连续体的高维研究中，科学家们发现了一种被称为“零点能量共振”的现象。这种现象表现为在一段连续的时间序列能量读数中，存在一个可以被精确分割成两个连续部分、且每个部分的能量扰动总和都恰好为零的区间。这种特殊的“对称”共振区间被认为是时空稳定的关键指标。

给定一个记录了 $N$ 个连续时间点能量扰动值的数组 $A$ 。数组中的元素为带符号整数。你的任务是找出其中最短的、能够表现出“零点能量共振”的子数组。

一个子数组被称为“可对称分割”，如果它能被分割成两个连续的子数组，且这两个子数组的元素和都为零。

形式化地说，对于一个子数组 $A[i..j]$ （下标从 $i$ 到 $j$ ），如果存在一个分割点 $k$ （其中 $i \le k < j$ ），使得： $\sum_{l=i}^{k} A[l] = 0 \quad \text{并且} \quad \sum_{l=k+1}^{j} A[l] = 0$ 那么，这个子数组 $A[i..j]$ 就是一个满足条件的共振区间。

你的目标是找到所有这类共振区间中，长度最短的一个或多个。你需要报告这个最短的长度，以及具有该最短长度的共振区间的数量。

输入描述

输入包含两行：
第一行是一个整数 $N$ ，代表时间序列的长度（数组 $A$ 的元素数量）。
第二行包含 $N$ 个整数 $a_i$ ，代表数组 $A$ 的元素。

输出描述

输出一行，包含两个整数，由空格隔开：
1. 满足条件的最短子数组的长度。
2. 具有该最短长度的子数组的个数。
如果不存在任何满足条件的子数组，则输出 -1 -1。

解题思路

题目的核心是寻找一个子数组，这个子数组可以被分割成两个连续且元素和都为零的部分。

1. 利用前缀和转化问题

这类关于连续子数组和的问题，通常是使用前缀和来优化的信号。我们定义一个前缀和数组 prefix，其中 prefix[x] 表示原数组从第 0 个元素到第 $x-1$ 个元素的和。通常我们令 prefix[0] = 0。那么，一个子数组 $A[a..b]$ 的和就可以表示为 prefix[b+1] - prefix[a]。

现在，我们将题目的条件用前缀和来表示：

$\sum_{l=i}^{k} A[l] = 0 \implies \text{prefix}[k+1] - \text{prefix}[i] = 0 \implies \text{prefix}[i] = \text{prefix}[k+1]$
$\sum_{l=k+1}^{j} A[l] = 0 \implies \text{prefix}[j+1] - \text{prefix}[k+1] = 0 \implies \text{prefix}[k+1] = \text{prefix}[j+1]$

将这两个条件合并，我们得出一个关键的结论：一个子数组 $A[i..j]$ 是“共振区间”的充要条件是，存在一个分割点 $k$ ，使得它们对应的前缀和满足： $\text{prefix}[i] = \text{prefix}[k+1] = \text{prefix}[j+1]$

这个子数组的长度为 $j - i + 1$ 。在前缀和数组中，它对应着两个索引的差值： $(j+1) - i$ 。

因此，原问题被巧妙地转化为了： 在 prefix 数组中，找到三个索引 a, b, c ( $a < b < c$ )，使得 prefix[a] == prefix[b] == prefix[c]，并且我们想要最小化 c - a 这个长度。

2. 使用哈希表进行高效查找

为了快速找到所有具有相同值的前缀和及其对应的索引，我们可以使用哈希表（或字典）。

构建哈希表：遍历前缀和数组，构建一个哈希表 indices_map，其键（key）为前缀和的值，其值（value）为一个列表，存储该前缀和出现过的所有索引。
寻找最短长度：
- 遍历 indices_map。对于每一个前缀和值，我们查看它对应的索引列表。
- 如果一个列表的长度小于 3，说明这个前缀和值最多只出现了两次，不可能构成 prefix[a] = prefix[b] = prefix[c] 的结构，直接跳过。
- 如果列表长度大于等于 3，例如 [idx_1, idx_2, ..., idx_m]，我们需要在这个列表中找到一对索引 (idx_p, idx_q)，使得它们的差值 idx_q - idx_p 最小，且它们之间至少还存在另一个索引 idx_r。
- 要使 idx_q - idx_p 最小且中间有值，我们应该选择 p=i, q=i+2。这样 b 就可以是 i+1。因此，我们需要计算的其实是 indices[i+2] - indices[i] 的最小值。

3. 最终算法

计算前缀和数组 prefix。
构建哈希表 indices_map，存储每个前缀和值出现的所有索引。
初始化 min_len = infinity 和 count = 0。
遍历 indices_map 中的每个索引列表 indices：
- 如果 indices 长度小于 3，跳过。
- 遍历 indices 列表，对于每个 i 从 0 到 len(indices)-3，计算 current_len = indices[i+2] - indices[i]。
- 用 current_len 更新 min_len 和 count：如果 current_len 更小，则更新 min_len 并重置 count 为 1；如果相等，则 count 加 1。
如果 min_len 仍为 infinity，输出 -1 -1，否则输出 min_len 和 count。

代码

cpp
java
python

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <limits>

using namespace std;

int main() {
    int n;
    cin >> n;
    vector<long long> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }

    map<long long, vector<int>> indices_map;
    indices_map[0].push_back(0); // prefix[0] = 0 at index 0

    long long current_sum = 0;
    for (int i = 0; i < n; ++i) {
        current_sum += a[i];
        indices_map[current_sum].push_back(i + 1);
    }

    long long min_len = numeric_limits<long long>::max();
    int count = 0;

    for (auto const& [sum, indices] : indices_map) {
        if (indices.size() < 3) {
            continue;
        }
        for (size_t i = 0; i <= indices.size() - 3; ++i) {
            long long current_len = indices[i + 2] - indices[i];
            if (current_len < min_len) {
                min_len = current_len;
                count = 1;
            } else if (current_len == min_len) {
                count++;
            }
        }
    }

    if (min_len == numeric_limits<long long>::max()) {
        cout << -1 << " " << -1 << endl;
    } else {
        cout << min_len << " " << count << endl;
    }

    return 0;
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long[] a = new long[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextLong();
        }

        Map<Long, List<Integer>> indicesMap = new HashMap<>();
        indicesMap.computeIfAbsent(0L, k -> new ArrayList<>()).add(0);

        long currentSum = 0;
        for (int i = 0; i < n; i++) {
            currentSum += a[i];
            indicesMap.computeIfAbsent(currentSum, k -> new ArrayList<>()).add(i + 1);
        }

        long minLen = Long.MAX_VALUE;
        int count = 0;

        for (List<Integer> indices : indicesMap.values()) {
            if (indices.size() < 3) {
                continue;
            }
            for (int i = 0; i <= indices.size() - 3; i++) {
                long currentLen = indices.get(i + 2) - indices.get(i);
                if (currentLen < minLen) {
                    minLen = currentLen;
                    count = 1;
                } else if (currentLen == minLen) {
                    count++;
                }
            }
        }

        if (minLen == Long.MAX_VALUE) {
            System.out.println("-1 -1");
        } else {
            System.out.println(minLen + " " + count);
        }
    }
}

from collections import defaultdict

def solve():
    n = int(input())
    a = list(map(int, input().split()))

    indices_map = defaultdict(list)
    indices_map[0].append(0)  # prefix[0] = 0 at index 0
    
    current_sum = 0
    for i, val in enumerate(a):
        current_sum += val
        indices_map[current_sum].append(i + 1)
        
    min_len = float('inf')
    count = 0

    for s in indices_map:
        indices = indices_map[s]
        if len(indices) < 3:
            continue
        
        for i in range(len(indices) - 2):
            current_len = indices[i+2] - indices[i]
            if current_len < min_len:
                min_len = current_len
                count = 1
            elif current_len == min_len:
                count += 1
                
    if min_len == float('inf'):
        print("-1 -1")
    else:
        print(min_len, count)

solve()

算法及复杂度

算法: 前缀和 + 哈希表
时间复杂度: $O(N)$ - 遍历数组计算前缀和并构建哈希表需要 $O(N)$ 。之后遍历哈希表中的所有索引列表，总的迭代次数也是 $O(N)$ 。
空间复杂度: $O(N)$ - 需要 $O(N)$ 空间存储前缀和数组（隐式计算）和哈希表。