C++程序：查找是否存在子数组的总和为0

给定正数和负数的数组，请查找是否存在大小至少为1的子数组其总和为0。

例子：

输入： {4, 2, -3, 1, 6}
输出： true
说明：
从索引1到3存在总和为0的子数组。

输入： {4, 2, 0, 1, 6}
输出 : true
说明：
从索引2到2存在总和为0的子数组。

输入： {-3, 2, 3, 1, 6}
输出： false

_练习 _

一个 简单的解决方案 是逐个考虑所有子数组，并检查每个子数组的总和。我们可以运行两个循环：外循环选择一个起始点i，内循环从i开始尝试所有子数组（实现请参见此处）。该方法的时间复杂度为O(n 2 )。
我们还可以 使用哈希 。想法是通过数组进行迭代，并为每个元素arr[i]计算从0到i的元素的总和（可以简单地处理为sum + = arr [i]）。如果当前总和已经在之前存在，则存在零和数组。使用哈希存储总和值，以便我们可以快速存储总和并找出当前总和是否在先前存在。
例子：

arr[] = {1, 4, -2, -2, 5, -4, 3}

如果我们考虑所有前缀和，我们可以
注意到当：
1）前缀和重复时，
2）前缀和变为0。

以上数组的前缀和为：
**1** , 5, 3, **1** , 6, 2, 5

由于前缀和1重复，因此我们有一个零总和子数组。

以下是上述方法的实现。

// C++程序：查找是否存在
// 总和为零的子数组
#include 
using namespace std;

bool subArrayExists(int arr[], int n)
{
    unordered_set sumSet;

    // 遍历整个数组并存储前缀和
    int sum = 0;
    for (int i = 0; i < n; i++) 
    {
        sum += arr[i];

        // 如果前缀和为0或已经存在，则 
        // 返回true
        if (sum == 0 
            || sumSet.find(sum) 
            != sumSet.end())
            return true;

        sumSet.insert(sum);
    }
    return false;
}

// 驱动代码
int main()
{
    int arr[] = { -3, 2, 3, 1, 6 };
    int n = sizeof(arr) / sizeof(arr[0]);
    if (subArrayExists(arr, n))
        cout << "发现一个总和为零的子数组";
    else
        cout << "没有这样的子数组存在！";
    return 0;
}