c++ - 查找具有给定总和的子数组

Question

问题陈述是:

Given an unsorted array of nonnegative integers, find a continous subarray which adds to a given number.

Examples:

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

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

Input: arr[] = {1, 4}, sum = 0
Output: No subarray found

基于对来自 this post 的解决方案的解释以下解决方案不适用于负数:

/* An efficient program to print subarray with sum as given sum */
#include<stdio.h>

/* Returns true if the there is a subarray of arr[] with sum equal to 'sum'
   otherwise returns false.  Also, prints the result */
int subArraySum(int arr[], int n, int sum)
{
    /* Initialize curr_sum as value of first element
       and starting point as 0 */
    int curr_sum = arr[0], start = 0, i;

    /* Add elements one by one to curr_sum and if the curr_sum exceeds the
       sum, then remove starting element */
    for (i = 1; i <= n; i++)
    {
        // If curr_sum exceeds the sum, then remove the starting elements
        while (curr_sum > sum && start < i-1)
        {
            curr_sum = curr_sum - arr[start];
            start++;
        }

        // If curr_sum becomes equal to sum, then return true
        if (curr_sum == sum)
        {
            printf ("Sum found between indexes %d and %d", start, i-1);
            return 1;
        }

        // Add this element to curr_sum
        if (i < n)
          curr_sum = curr_sum + arr[i];
    }

    // If we reach here, then no subarray
    printf("No subarray found");
    return 0;
}

我尝试考虑了几种不同的输入场景，但我想不出输入数组包含负数而不会产生正确输出的情况。这是一个有效的负数输入数组:

int arr[] = { 15, 14, -2, 3, -5, 14};

当帖子说该解决方案不适用于负数时，指的是哪些输入案例？

Answer 1

这个解决方案依赖于这样一个事实，即当我们删除一个元素时，我们的总和会减少，但负数与这个假设相矛盾。

最短的例子是这样的情况 -1 5 2 当我们寻找和为5的子数组时，操作如下:

add -1, sum = -1
add 5, sum = 4
add 2, sum = 6
remove -1, sum = 7
remove 5, sum = 2

我们已经到了列表的末尾，但还没有找到所需的子数组。