Consecutive sequence with sum 0

简介:

You are given an integer array which contains positive integers, zero and negetive integers
count how many consecutive sequences in this array make a sum of 0.

exmaple
int[] a = {4, -1, 2, 1, -2, -1, 5, 0} ;
The result is 2
-1, 2, 1, -2, makes a sum of 0
2, 1, -2, -1, makes a sum of 0
0 makes a sum of 0

consider a consecutive sequence in array a, say xi, ... xj, if xi + ... + xj = 0, then x0 + .. + x(i-1) = x0 + .. + xj
so we can compute all the prefix sum of array a, and see whether there are equal elements among these sum
if there is, then there must be some consecutive sequence, makes sum of 0

 

Code

 

本文转自zdd博客园博客,原文链接:http://www.cnblogs.com/graphics/archive/2009/06/09/1499768.html,如需转载请自行联系原作者

相关文章
Longest Consecutive Sequence
Given an unsorted array of integers, find the length of the longest consecutive elements sequence. For example,Given [100, 4, 200, 1, 3, 2],The longest consecutive elements sequence is [1, 2, 3, 4].
845 0
|
算法 C#
算法题丨Longest Consecutive Sequence
描述 Given an unsorted array of integers, find the length of the longest consecutive elements sequence.
1134 0
|
算法
LeetCode 128. Longest Consecutive Sequence
给定一个未排序的整数数组,找出最长连续序列的长度。 要求算法的时间复杂度为 O(n)。
101 0
LeetCode 128. Longest Consecutive Sequence
[LeetCode] Longest Consecutive Sequence
This problem is not very intuitive at first glance. However, the final idea should be very self-explanatory.
790 0
1104. Sum of Number Segments (20) consecutive subsequence 每个数出现的次数
Given a sequence of positive numbers, a segment is defined to be a consecutive subsequence.
995 0
the smallest positive number
2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder. What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?   程序比较好编,就是考验计算机。
911 0
Maximum Subsequence Sum
最大连续子列和问题,在此给出题解 (浙大PTA https://pintia.cn/problem-sets/16/problems/665)