题解 | 能量共振

动态规划，加入一个新的数，就往前遍历，如果找到两个组加和为0的数组，并且这两个数组长度小于当前记录的结果，就更新当前结果。主要加入一些判断条件，提前结束二层循环，不然时间复杂度会超过。

#include <iostream>
#include <vector>
using namespace std;


void solve(vector<int>& datas, vector<int>& result) {
    int n = datas.size();
    for (int i = 0; i < n; i++) {
        int min = -1;
        int sum = datas[i];
        int k = -1;
        int start = -2;
        // 如果本省sum就是0，单独讨论
        if (sum == 0){
            k = i;
            start = -1;
        }
        int len = -1;
        for (int j = i - 1; j >= 0; j--) {
            len = i - j + 1;
            if (len > result[0] && result[0] != -1) break;
            sum += datas[j];
            if (sum == 0) {
                if (k == -1) {
                    k = j;
                    start = -1;
                    if (j != 0) {
                        j--;
                        sum = datas[j];
                    }
                }
                else if (start == -1) {
                    start = j;
                    break;
                }
            }
        }
        if (k != -1 && start != -1) {
            min =  i - start + 1;
            if (result[0] == -1 || result[0] > min) {
                result[0] = min;
                result[1] = 1;
            }
            else if (result[0] == min) result[1]++;
        }
    }
    // 打印
    cout << result[0] << ' ' << result[1];

    return ;
}


int main() {
    int n;
    cin >> n;
    vector<int> datas(n);
    for (int i = 0; i < n; i++) cin >> datas[i];
    vector<int> result(2, -1);

    solve(datas, result);

    return 0;
}