具有给定和的子阵列

Question

给定一个大小为N的非负整数的未排序数组，找到一个与给定数S相加的连续子数组。

输入：
输入的第一行包含一个整数T，表示测试用例的数量。接下来是T测试用例。每个测试用例由两行组成。每个测试用例的第一行是N和S，其中N是数组的大小，S是和。每个测试用例的第二行包含N个表示数组元素的空格分隔整数。

输出：
对于每个测试用例，在新行中，如果sum等于子数组，则从左侧打印第一个出现子数组的开始和结束位置（1索引），否则打印-1。

约束条件：

1 <= T <= 100
1 <= N <= 107
1 <= Ai <= 1010

示例：
输入：

2
5 12
1 2 3 7 5
10 15
1 2 3 4 5 6 7 8 9 10

输出：

2 4
1 5

我的代码：

#include <iostream>

using namespace std;

int main() {
    int t, n, s, a[1000], result[1000];
    cin >> t;
    for (int i = 0; i < t; i++) {
        result[i * 2] = -1;
        cin >> n >> s;
        for (int j = 0; j < n; j++) {
            cin >> a[j];
        }
        int flag = 0;
        for (int j = 0; j < n; j++) {
            if (flag == 0) {
                int sum = 0;
                for (int k = j; k < n && sum < s; k++) {
                    sum += a[k];
                    if (sum == s) {
                        result[i * 2] = j + 1;
                        result[(i * 2) + 1] = k + 1;
                        flag = 1;
                        break;
                    }
                }
            }
        }
    }
    for (int i = 0; i < t * 2; i += 2) {
        if (result[i] != -1) {
            cout << result[i] << " " << result[i + 1] << endl;
        } else {
            cout << result[i];
        }
    }
}

结果：
错误答案。！！！错误答案

对于多个测试用例（TCs），您的代码可能无法正常工作。

代码失败的第一个测试用例：

输入：

4 225
9 45 10 190

其正确输出为：

-1

您的代码输出为：

-1-1-1-138 42

Answer 1

我刚刚发现了这个：https://www.youtube.com/watch?v=G0ocgTgW464但是我相信时间复杂度是O（n*log（n）），因为map::find是O（log（n））