您有一个数组，需要计算其中连续子数组的个数，使得其和为零。
example:
1) 0 ,1,-1,0 => 6 {{0},{1,-1},{0,1,-1},{1,-1,0},{0}};
2) 5, 2, -2, 5 ,-5, 9 => 3.
使用O(n^2)复杂度可以完成。我正在努力寻找比这更低的复杂度解决方案。
寻找连续子数组的数量，其和为零。
7
- dead programmer
3
我尝试使用http://www.geeksforgeeks.org/find-subarray-with-given-sum/，但它并没有解决我的问题。 - dead programmer
在你的第一个例子中，{0} 看起来是重复的。另外还可以是 {0,1,-1,0}。 - Kulbhushan Singh
正确和{0}被认为是两次重复，允许子集的重复。 - dead programmer
6个回答
9
考虑数组S[0..N] - 数组的前缀和，即对于从0到N的k，S[k] = A[0] + A[1] + ... + A[k-1]。
现在，当且仅当S[R] = S[L]时，从L到R-1的元素的和为零。这意味着您必须找到指标数量0 <= L < R <= N，使得S[L] = S[R]。
此问题可以使用哈希表解决。在维护S[]元素的同时迭代，对于每个值X，在已处理的S[]部分中遇到的次数应该存储在哈希映射中，其中数字X是键，计数H[X]是值。当您遇到新元素S[i]时，将H[S[i]]添加到答案中（这些对应于以(i-1)-st元素结尾的子字符串），然后将H[S[i]]增加一。
请注意，如果数组元素的绝对值之和很小，则可以使用简单数组而不是哈希表。平均复杂度为线性。
以下是代码：
现在，当且仅当S[R] = S[L]时，从L到R-1的元素的和为零。这意味着您必须找到指标数量0 <= L < R <= N，使得S[L] = S[R]。
此问题可以使用哈希表解决。在维护S[]元素的同时迭代，对于每个值X，在已处理的S[]部分中遇到的次数应该存储在哈希映射中，其中数字X是键，计数H[X]是值。当您遇到新元素S[i]时，将H[S[i]]添加到答案中（这些对应于以(i-1)-st元素结尾的子字符串），然后将H[S[i]]增加一。
请注意，如果数组元素的绝对值之和很小，则可以使用简单数组而不是哈希表。平均复杂度为线性。
以下是代码：
long long CountZeroSubstrings(vector<int> A) {
int n = A.size();
vector<long long> S(n+1, 0);
for (int i = 0; i < n; i++)
S[i+1] = S[i] + A[i];
long long answer = 0;
unordered_map<long long, int> H;
for (int i = 0; i <= n; i++) {
if (H.count(S[i]))
answer += H[S[i]];
H[S[i]]++;
}
return answer;
}
- stgatilov
1
使用易读变量的C#版本@stgatilov答案 https://dev59.com/Bo3da4cB1Zd3GeqPviXO#31489960
int[] sums = new int[arr.Count() + 1];
for (int i = 0; i < arr.Count(); i++)
sums[i + 1] = sums[i] + arr[i];
int numberOfFragments = 0;
Dictionary<int, int> sumToNumberOfRepetitions = new Dictionary<int, int>();
foreach (int item in sums)
{
if (sumToNumberOfRepetitions.ContainsKey(item))
numberOfFragments += sumToNumberOfRepetitions[item];
else
sumToNumberOfRepetitions.Add(item, 0);
sumToNumberOfRepetitions[item]++;
}
return numberOfFragments;
如果您不仅想要总和为零，而是任何数字k，则以下是提示：
int numToFind = currentSum - k;
if (sumToNumberOfRepetitions.ContainsKey(numToFind))
numberOfFragments += sumToNumberOfRepetitions[numToFind];
- Lev
1
通过在数组遍历期间保持一个和的哈希表，可以在线性时间内解决这个问题。然后可以直接从重复访问和的计数中计算子集的数量。
Haskell版本:
import qualified Data.Map as M
import Data.List (foldl')
f = foldl' (\b a -> b + div (a * (a + 1)) 2) 0 . M.elems . snd
. foldl' (\(s,m) x -> let s' = s + x in case M.lookup s' m of
Nothing -> (s',M.insert s' 0 m)
otherwise -> (s',M.adjust (+1) s' m)) (0,M.fromList[(0,0)])
输出：
*Main> f [0,1,-1,0]
6
*Main> f [5,2,-2,5,-5,9]
3
*Main> f [0,0,0,0]
10
*Main> f [0,1,0,0]
4
*Main> f [0,1,0,0,2,3,-3]
5
*Main> f [0,1,-1,0,0,2,3,-3]
11
- גלעד ברקן
2
给定一个由N个零组成的数组，每个非空子数组的和都为零，因此答案必须是N*(N+1)/2。然而，你的解决方案只返回形如(2^s - 1)的数字。这不是错误吗？
另外，第一个数组的答案似乎是6。 - stgatilov
@stgatilov 你是正确的 - 我犯了一个错误，计算了所有子集，而不是所有连续子集 - 谢谢。我更正了公式。 - גלעד ברקן
0
https://www.techiedelight.com/find-sub-array-with-0-sum/
这将是一个精确的解决方案。
# Utility function to insert <key, value> into the dict
def insert(dict, key, value):
# if the key is seen for the first time, initialize the list
dict.setdefault(key, []).append(value)
# Function to print all sub-lists with 0 sum present
# in the given list
def printallSublists(A):
# create an empty -dict to store ending index of all
# sub-lists having same sum
dict = {}
# insert (0, -1) pair into the dict to handle the case when
# sub-list with 0 sum starts from index 0
insert(dict, 0, -1)
result = 0
sum = 0
# traverse the given list
for i in range(len(A)):
# sum of elements so far
sum += A[i]
# if sum is seen before, there exists at-least one
# sub-list with 0 sum
if sum in dict:
list = dict.get(sum)
result += len(list)
# find all sub-lists with same sum
for value in list:
print("Sublist is", (value + 1, i))
# insert (sum so far, current index) pair into the -dict
insert(dict, sum, i)
print("length :", result)
if __name__ == '__main__':
A = [0, 1, 2, -3, 0, 2, -2]
printallSublists(A)
- kim.sardine
0
我觉得可以用DP来解决：
设状态为：
DP[i][j] 表示使用以i结尾的所有子数组组成j的方法数！
转移：
对于初始步骤中的每个元素，
将使用i个元素形成Element[i]的方法数增加1，即使用从i开始并以i结束的长度为1的子数组。
DP[i][Element[i]]++;
然后对于每个 j 在范围 [-任何元素的最高幅值，任何元素的最高幅值] 中
DP[i][j]+=DP[i-1][j-Element[i]];
那么你的答案将是所有DP [i] [0]的总和（使用以i结尾的子数组形成0的方法数），其中i的范围从1到元素数量
复杂度为O（MOD任何元素的最高幅度*元素数量）
- Shubham Sharma
-2
我不知道我的建议的复杂性会是什么样子，但我有一个想法 :)
你可以尝试从主数组中减少那些对解决方案没有贡献的元素
假设元素为-10、5、2、-2、5、7、-5、9、11、19
所以你可以看到-10、9、11和19是元素
这些元素在你的例子中永远不会有用来使总和等于0
所以尝试从主数组中删除-10、9、11和19
为了做到这一点，你可以
1) create two sub array from your main array
`positive {5,7,2,9,11,19}` and `negative {-10,-2,-5}`
2) remove element from positive array which does not satisfy condition
condition -> value should be construct from negative arrays element
or sum of its elements
ie.
5 = -5 //so keep it //don't consider the sign
7 = (-5 + -2 ) // keep
2 = -2 // keep
9 // cannot be construct using -10,-2,-5
same for all 11 and 19
3) remove element form negative array which does not satisfy condition
condition -> value should be construct from positive arrays element
or sum of its elements
i.e. -10 // cannot be construct so discard
-2 = 2 // keep
-5 = 5 // keep
最后，您得到了一个包含-2、-5、5、7、2的数组。创建所有可能的子数组并检查其是否相加等于0。
（注意：如果您的输入数组包含0，请在最终数组中添加所有0）。
- Vishnu
2
- 如果所有元素都是-1和1，那么你的修剪不会产生任何结果。
- 复杂度是不确定的，但不低于O(N^2)。
@stgatilov 如果数据只包含像你所说的-1和1这样有用的元素，那么这是没有帮助的，也不会减少任何复杂性，但考虑到包含许多非必需元素的数据集（这也是空闲情况），在这种情况下，这肯定会减少复杂性 :) - Vishnu
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接