您有一个数组,需要计算其中连续子数组的个数,使得其和为零。
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)复杂度可以完成。我正在努力寻找比这更低的复杂度解决方案。
您有一个数组,需要计算其中连续子数组的个数,使得其和为零。
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)复杂度可以完成。我正在努力寻找比这更低的复杂度解决方案。
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;
}
使用易读变量的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];
通过在数组遍历期间保持一个和的哈希表,可以在线性时间内解决这个问题。然后可以直接从重复访问和的计数中计算子集的数量。
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
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)
我觉得可以用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任何元素的最高幅度*元素数量)
我不知道我的建议的复杂性会是什么样子,但我有一个想法 :)
你可以尝试从主数组中减少那些对解决方案没有贡献的元素
假设元素为-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