c++ - 使用 map 查找具有给定总和(带负数)的子数组

Question

考虑以下问题陈述:

Given an unsorted array of integers, find a subarray which adds to a given number. If there are more than one subarrays with sum as the given number, print any of them.

Examples:

Input: arr[] = {1, 4, 20, 3, 10, 5}, sum = 33
Ouptut: Sum found between indexes 2 and 4

Input: arr[] = {10, 2, -2, -20, 10}, sum = -10
Ouptut: Sum found between indexes 0 to 3

Input: arr[] = {-10, 0, 2, -2, -20, 10}, sum = 20
Ouptut: No subarray with given sum exists

在此site , 提出了以下线性时间解决方案，其中涉及在算法遍历数组时使用映射来存储当前子集的总和:

// Function to print subarray with sum as given sum
void subArraySum(int arr[], int n, int sum)
{
    // create an empty map
    unordered_map<int, int> map;

    // Maintains sum of elements so far
    int curr_sum = 0;

    for (int i = 0; i < n; i++)
    {
        // add current element to curr_sum
        curr_sum = curr_sum + arr[i];

        // if curr_sum is equal to target sum
        // we found a subarray starting from index 0
        // and ending at index i
        if (curr_sum == sum)
        {
            cout << "Sum found between indexes "
                 << 0 << " to " << i << endl;
            return;
        }

        // If curr_sum - sum already exists in map
        // we have found a subarray with target sum
        if (map.find(curr_sum - sum) != map.end())
        {
            cout << "Sum found between indexes "
                 << map[curr_sum - sum] + 1
                 << " to " << i << endl;
            return;
        }

        map[curr_sum] = i;
    }

    // If we reach here, then no subarray exists
    cout << "No subarray with given sum exists";
}
// Driver program to test above function
int main()
{
    int arr[] = {10, 2, -2, -20, 10};
    int n = sizeof(arr)/sizeof(arr[0]);
    int sum = -10;

    subArraySum(arr, n, sum);

    return 0;
}

对于帖子中提供的测试用例，第二个 if 语句检查是否从未输入 current_sum - sum。相反，总和会在第一个 if 语句中找到并打印出来。 所以这里有几点混淆:

1:在 map 中查找current_sum-sum的目的是什么？

2:在什么情况下甚至会输入第二个 if 语句来将 map 用于解决问题？

Answer 1

    curr_sum = curr_sum + arr[i];

这里:

curr_sum holds the sum of all the entries(up to arr[i]) starting from arr[0]

if (curr_sum == sum)
{
    cout << "Sum found between indexes "
         << 0 << " to " << i << endl;
    return;
}

这里:

The if condition checks if the curr_sum is equal to the given sum. Remember, curr_sum holds the sum starting from arr[0].

因此，如果您的结果子数组的索引是 2 和 4，则上述条件是不够的。

Input: arr[] = {1, 4, 20, 3, 10, 5}, sum = 33
Ouptut: Sum found between indexes 2 and 4

在那个例子中，

when i = 4, curr_sum would be 38. But if you take 1 and 4 out(arr[0] and arr[1] which is a subarray), you get 33.

    if (map.find(curr_sum - sum) != map.end())
    {
        cout << "Sum found between indexes "
             << map[curr_sum - sum] + 1
             << " to " << i << endl;
        return;
    }

    map[curr_sum] = i;

上面的代码就是这样做的。

 map[curr_sum] = i;

map 以子数组和(索引 0 和 i 之间的 arr 之和)为键存储索引值 (i)。因此，对于示例，它将是:

• map [1]=0
• map [5]=1
• map [25]=2
• map [28]=3
• map [38]=4

这段代码:

    map.find(curr_sum - sum)

搜索 map 是否有带键(curr_sum - sum)的条目。

In our example, when i = 4, curr_sum would be 38 and sum as given would be 33. If we eliminate the subarray arr[0,2], we get 33. So, map.find(curr_sum - sum) => map.find(38-33) is a hit since we have entry map[5] = 1.

希望这能让你清醒