c++ - 使用 unordered_map 确定子数组索引失败的函数

Question

我正在尝试计算输入数组“arr”的元素，该数组用于确定子数组的最大和，以下称为“maxSum”(在别处确定，并确认是正确的)。函数 showSubArray() 接受数组 arr、数组长度 n 和 maxSum 作为参数。输入数组是正整数和负整数。下面是一组带有结果的测试数组。失败意味着 arr[0] 被打印到屏幕上，并用一个空格无限地分隔它们。我在输入中看不到任何可识别的模式会导致这种情况。非常感谢任何帮助，我不喜欢 unordered_map 方法。从确定 maxSum 的函数获取索引不是可接受的解决方案。

#include <unordered_map>
#include <iostream>
using std::cout;

int main() {

   //int arr[] = { 1, 4, -9, 8, 1, 3, 3, 1, -1, -4, -6, 2, 8, 19, -10, -11 };
   //   runs ok, inputs: n=16, maxSum = 34

   //int arr[] = { 2, 9, 8, 6, 5, -11, 9, -11, 7, 5, -1, -8, -3, 7, -2 };
   // ***fails, inputs: n=15, maxSum = 30

   //int arr[] = { 10, -11, -1, -9, 33, -45, 23, 24, -1, -7, -8, 19 };
   //    runs ok, n=12, maxSum = 50

   //int arr[] = { 31, -41, 59, 26, -53, 58, 97, -93, -23, 84 };
   //    runs ok n=10 maxSum = 187

   //int arr[] = { 3, 2, 1, 1, -8, 1, 1, 2, 3 };
   // ***fails, inputs: n=9 maxSum = 7

   int arr[] = { 12, 99, 99, -99, -27, 0, 0, 0, -3, 10 };
   // ***fails, n=10 maxSum = 210

   //int arr[] = { -2, 1, -3, 4, -1, 2, 1, -5, 4 };
   //    runs ok, inputs: n=9 maxSum = 6

   showSubArray(arr, n, maxSum);
   return 0;
}


void showSubArray(int arr[], int n, int maxSum) {
    std::unordered_map<int, int> aMap;
    int accumulator = 0;

    for (int i = 0; i < n; i++) {
        accumulator += arr[i];

        if (accumulator == maxSum) {
            for(int j = 0; j <= i; j++) {
       // ACB found error here     ^ (I had it as "i")
                cout << arr[j];
                cout << " ";
            }
            cout << '\n';
            return;
        }

        if (aMap.find(accumulator - maxSum) != aMap.end()) {
            for (int j = aMap[accumulator - maxSum] + 1; j <= i; j++) {
                cout << arr[j];
                cout << " ";
            }
            cout << '\n';
            return;
        }

        aMap[accumulator] = i;
    }

    cout << "Subarray not found!\n";
}

Answer 1

if (accumulator == maxSum) { 
    for(int j = 0; j <= i; i++) { 

你在这里递增 i 但你想递增 j 因为 0 总是小于 i 因为 i > 0 直到它溢出