给定一个整数数组,如[1, 2, -3, 1]
,查找是否存在一个子序列的总和为0
,并返回它(例如[1, 2, -3]
或[2, -3, 1]
)。
检查每个子序列的时间复杂度是O(n^2)
,效率太低。有什么改进的想法吗?
给定一个整数数组,如[1, 2, -3, 1]
,查找是否存在一个子序列的总和为0
,并返回它(例如[1, 2, -3]
或[2, -3, 1]
)。
检查每个子序列的时间复杂度是O(n^2)
,效率太低。有什么改进的想法吗?
创建一个新的数组,其中每个元素均等于前面所有元素的和再加上当前元素。
输入:
1 4 -3 -4 6 -7 8 -5
Becomes:
1 5 2 -2 4 -3 5 0
^ ^
然后查找结果数组中匹配的元素。
由于这些代表函数整体变化为零的位置,你会发现如果它们的位置是i和k,则子序列(i+1,k)是一个零和子序列。(在这种情况下,[2:6]).
此外,表格中的任何零都表示子序列(0,k)是一个零和子序列。使用哈希表或其他快速碰撞定位器进行查找可以使其O(N)执行。
在哈希表中进行累加,并将累加值与数组索引一起存储。
如果您曾经得到一个已经出现过的累加值,则返回哈希表中索引值+1,以及当前索引值。此解决方案时间复杂度为O(n)。
不需要新的数组。由于哈希表,空间复杂度为O(N)。
Python实现代码:
input = [1, 4, -3, -4, 6, -7, 8, -5]
map = {}
sum = 0
for i in range(len(input)):
sum += input[i]
if sum in map:
print map[sum][0] + 1, "to", i
map[sum] = (i, sum)
请注意,重复的子序列将不会被显示。例如:如果(1到2)是一个子序列,而(3到4)、(1到4)将不会被显示。您可以通过在Map的每个位置存储列表来实现此行为:
for x in map[sum]:
print x[0]+1, "to", i
map[sum].append((i, sum))
public static int countAllSubSequenceForZeroSum(int[] array) {
int count = 0;
Map<Integer, Integer> encounteredSum = new HashMap<>();
int prev = array[0];
if(prev == 0) {
count++;
System.out.println("Found at index: "+0);
}
for (int i = 1; i < array.length; i++) {
prev += array[i];
if(encounteredSum.containsKey(prev)) {
System.out.println("Found at index: "+i+ " start index: "+encounteredSum.get(prev));
printSequenceForZeroSum(array, i);
count++;
} else {
encounteredSum.put(prev, i);
}
}
return count;
}
public static void printSequenceForZeroSum(int[] array, int endIndex) {
int sum = array[endIndex];
while(sum!=0) {
System.out.print(array[endIndex]+ " ");
sum += array[--endIndex];
}
System.out.println(array[endIndex]);
}
pair<int, int> FindSubsequenceSum(const vector<int>& arr)
{
map<int, int> sumMap;
map<int, int>::iterator it;
int sum = 0;
for (int i = 0; i < arr.size(); i++)
{
sum += arr[i];
it = sumMap.find(sum);
if (it != sumMap.end())
{
return make_pair(it->second + 1, i);
} else {
sumMap.insert(make_pair(sum, i));
}
}
int main()
{
int arr[] = {1,4,-3,-4,6,-7,8,-5};
vector<int> input(arr, arr + sizeof(arr) / sizeof(arr[0]));
pair<int, int> result = FindSubsequenceSum(input);
cout << "(" << result.first << "," << result.second << ")" << endl;
return 0;
}
Output:
(2,6)
List(1,2,3,4).scan(0){_+_}
结果将会是List(0, 1, 3, 6, 10)。
或者你可以:
List(1,2,3,4).scan(0){_+_}.tail
获取List(1, 3, 6, 10)