# 查找是否有一個總和為 0 的子數組 > 原文： [https://www.geeksforgeeks.org/find-if-there-is-a-subarray-with-0-sum/](https://www.geeksforgeeks.org/find-if-there-is-a-subarray-with-0-sum/) 給定一個正負數數組，請查找是否存在一個總和為 0 的子數組（大小至少為一個）。 **示例**： ``` Input: {4, 2, -3, 1, 6} Output: true There is a subarray with zero sum from index 1 to 3. Input: {4, 2, 0, 1, 6} Output: true There is a subarray with zero sum from index 2 to 2. Input: {-3, 2, 3, 1, 6} Output: false There is no subarray with zero sum. ``` **簡單解決方案**是一個個地考慮所有子數組，并檢查每個子數組的總和。 我們可以運行兩個循環：外部循環選擇起始點 i，內部循環嘗試從 i 開始的所有子數組（有關實現，請參見[此](https://www.geeksforgeeks.org/find-subarray-with-given-sum/)）。 該方法的時間復雜度為 `O(n^2)`。 我們還可以**使用哈希**。 想法是遍歷數組，對于每個元素 arr [i]，計算從 0 到 i 的元素總和（這可以簡單地通過 sum + = arr [i]來完成）。 如果當前總和是以前看過的，則有一個零總和數組。 散列用于存儲總和值，以便我們可以快速存儲總和并找出當前總和是否之前被查看過。 范例： ``` arr[] = {1, 4, -2, -2, 5, -4, 3} If we consider all prefix sums, we can notice that there is a subarray with 0 sum when : 1) Either a prefix sum repeats or 2) Or prefix sum becomes 0. Prefix sums for above array are: 1, 5, 3, 1, 6, 2, 5 Since prefix sum 1 repeats, we have a subarray with 0 sum. ``` 以下是上述方法的實現。 ## C++ ```cpp // A C++ program to find if there is a zero sum // subarray #include <bits/stdc++.h> using namespace std; bool subArrayExists(int arr[], int n) { ????unordered_set<int> sumSet; ????// Traverse through array and store prefix sums ????int sum = 0; ????for (int i = 0 ; i < n ; i++) ????{ ????????sum += arr[i]; ????????// If prefix sum is 0 or it is already present ????????if (sum == 0 || sumSet.find(sum) != sumSet.end()) ????????????return true; ????????sumSet.insert(sum); ????} ????return false; } // Driver code int main() { ????int arr[] =? {-3, 2, 3, 1, 6}; ????int n = sizeof(arr)/sizeof(arr[0]); ????if (subArrayExists(arr, n)) ????????cout << "Found a subarray with 0 sum"; ????else ????????cout << "No Such Sub Array Exists!"; ????return 0; } ```