给定一个正数和负数的数组，找出是否有一个和为0的子数组（大小至少为1）。
null
例如：
输入： {4, 2, -3, 1, 6} 输出： 符合事实的 说明： 在索引1到3之间有一个零和的子数组。
输入： {4, 2, 0, 1, 6} 输出 ：对
解释 :
第三个元素是零。单个元素也是一个子数组。
输入： {-3, 2, 3, 1, 6} 输出： 错误的
A. 简单解决方案 是一个一个地考虑所有子数组，并检查每个子数组的和。我们可以运行两个循环：外循环选择一个起点i，内循环尝试从i开始的所有子数组（参见 这 （用于实施）。该方法的时间复杂度为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 cannotice that there is a subarray with 0sum when :1) Either a prefix sum repeats or2) Or prefix sum becomes 0.Prefix sums for above array are:1, 5, 3, 1, 6, 2, 5Since prefix sum 1 repeats, we have a subarraywith 0 sum.
以下是上述方法的实现。
C++
// 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; } |
JAVA
// A Java program to find // if there is a zero sum subarray import java.util.HashSet; import java.util.Set; class ZeroSumSubarray { // Returns true if arr[] // has a subarray with sero sum static Boolean subArrayExists( int arr[]) { // Creates an empty hashset hs Set<Integer> hs = new HashSet<Integer>(); // Initialize sum of elements int sum = 0 ; // Traverse through the given array for ( int i = 0 ; i < arr.length; i++) { // Add current element to sum sum += arr[i]; // Return true in following cases // a) Current element is 0 // b) sum of elements from 0 to i is 0 // c) sum is already present in hash set if (arr[i] == 0 || sum == 0 || hs.contains(sum)) return true ; // Add sum to hash set hs.add(sum); } // We reach here only when there is // no subarray with 0 sum return false ; } // Driver code public static void main(String arg[]) { int arr[] = { - 3 , 2 , 3 , 1 , 6 }; if (subArrayExists(arr)) System.out.println( "Found a subarray with 0 sum" ); else System.out.println( "No Such Sub Array Exists!" ); } } |
Python3
# A python program to find if # there is a zero sum subarray def subArrayExists(arr, n): # traverse through array # and store prefix sums n_sum = 0 s = set () for i in range (n): n_sum + = arr[i] # If prefix sum is 0 or # it is already present if n_sum = = 0 or n_sum in s: return True s.add(n_sum) return False # Driver code arr = [ - 3 , 2 , 3 , 1 , 6 ] n = len (arr) if subArrayExists(arr, n) = = True : print ( "Found a sunbarray with 0 sum" ) else : print ( "No Such sub array exits!" ) # This code is contributed by Shrikant13 |
C#
// A C# program to find if there // is a zero sum subarray using System; using System.Collections.Generic; class GFG { // Returns true if arr[] has // a subarray with sero sum static bool SubArrayExists( int [] arr) { // Creates an empty HashSet hM HashSet< int > hs = new HashSet< int >(); // Initialize sum of elements int sum = 0; // Traverse through the given array for ( int i = 0; i < arr.Length; i++) { // Add current element to sum sum += arr[i]; // Return true in following cases // a) Current element is 0 // b) sum of elements from 0 to i is 0 // c) sum is already present in hash set if (arr[i] == 0 || sum == 0 || hs.Contains(sum)) return true ; // Add sum to hash set hs.Add(sum); } // We reach here only when there is // no subarray with 0 sum return false ; } // Main Method public static void Main() { int [] arr = { -3, 2, 3, 1, 6 }; if (SubArrayExists(arr)) Console.WriteLine( "Found a subarray with 0 sum" ); else Console.WriteLine( "No Such Sub Array Exists!" ); } } |
Javascript
// A Javascript program to // find if there is a zero sum subarray const subArrayExists = (arr) => { const sumSet = new Set(); // Traverse through array // and store prefix sums let sum = 0; for (let i = 0 ; i < arr.length ; i++) { sum += arr[i]; // If prefix sum is 0 // or it is already present if (sum === 0 || sumSet.has(sum)) return true ; sumSet.add(sum); } return false ; } // Driver code const arr = [-3, 2, 3, 1, 6]; if (subArrayExists(arr)) console.log( "Found a subarray with 0 sum" ); else console.log( "No Such Sub Array Exists!" ); |
输出
No Such Sub Array Exists!
时间复杂性 在假设我们有良好的哈希函数，允许在O（1）时间内进行插入和检索操作的情况下，这个解决方案的一部分可以被视为O（n）。 空间复杂性 ：O（n）。在这里，我们需要额外的空间为无序的_集插入数组元素。
练习： 扩展上述程序，打印所有子数组的起始索引和结束索引的总和为0。 本文由 奇拉格·古普塔 。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请发表评论
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
