improve time complexity of algo find_continuous_subsequences

Hi, i have an array (vector<int> = {-1, -3, 4, 5, -2, -4, 6}) and want to print all continuous subsequences in the array which sum of 0. im wondering how you can make it faster than my version, which is O(n^2)!?

the array:

-1, -3, 4, 5, -2, -4, 6

the sequences which sum up to 0:

sum(-1 -3 4) = 0
sum(6 -4 -2) = 0
sum(-3 4 5 -2 -4) = 0

my algo:

#include <iostream>
#include <string>
#include <limits>
#include <vector>
#include <algorithm>
using namespace std;

vector<int> add_numbers_in_range(vector<int> &vec, int start, int end) {
	vector<int> v;

	for(int i = start; i <= end; i++) {
		v.push_back(vec[i]);
	}	

	return v;
}

vector<vector<int>> find_continuous_subsequences(vector<int> &vec, int sum) {
	pair<int,int> max_sum_range;
	int current_sum = 0;
	vector<vector<int>> v;

	for(int i = 0; i < vec.size(); i++) {
		int current_sum = 0;

		for(int j = i; j < vec.size(); j++) {
			current_sum += vec[j];

			if(current_sum == sum) {
				v.push_back(add_numbers_in_range(vec, i, j));
			}
		}
	}

	return v;
}

int main() {
	// your code goes here

	vector<int> vec = {-1, -3, 4, 5, -2, -4, 6};
	vector<vector<int>> nums = find_continuous_subsequences(vec, 0);

	for(int i = 0; i < nums.size(); i++) {
		for(int j = 0; j < nums[i].size(); j++) {
			cout << nums[i][j] << ' ';
		}
		cout << '\n';
	}

	return 0;
}

a little but:

if(current_sum == sum) {

whould be:

if(current_sum == sum && j > i) {

otze

O(n^2) is tight.

consider the string

1 -1 1 -1 1 -1 1 -1 1 -1 1 -1

or even simpler

0 0 0 0 0 0 0 ...

in both cases there are O(n^2) matches. Btw: as you create the concrete substring of all these substrings your algorithm is O(n^3). O(n^2) is only for the start/end indices of the range.

//edit if you expect a very low number of matches in a big string of numbers you might get better.

consider the running sum of all elements prefixed with 0:

-1, -3, 4, 5, -2, -4, 6

=>

int sum[] ={0, -1, -4, 0, 5, 3, 1, 5}

than it holds:
[i,j) is a range with sum 0 iff sum[i]==sum[j];

and finding equal elements is n log(n) using sorting.

@otze: i see, whats your idea to improve it?

what is sum[i] and sum [j] ?

otze

otze schrieb:

consider the running sum of all elements prefixed with 0:
-1, -3, 4, 5, -2, -4, 6
=>
int sum[] ={0, -1, -4, 0, 5, 3, 1, 5}

you only have one 0 in your running sum besides the 0 at the start...so you only find 1 subsequence?

FTFY:

otze schrieb:

int sum[] ={0, -1, -4, 0, 5, 3, -1, 5}

algoman1 schrieb:

you only have one 0 in your running sum besides the 0 at the start...so you only find 1 subsequence?

Read carefully what he told you:

otze schrieb:

than it holds:
[i,j) is a range with sum 0 iff sum[i]==sum[j];

You are looking for pairwise equal numbers, not only zero entries.

Example:
-1, -3, 4, 5, -2, -4, 6
=> int sum[] ={0, -1, -4, 0, 5, 3, -1, 5}

Look at the pair of -1 with indices i=1 and j=6.
Now it holds that the subsequence [1,6) = [1,5] sums up to zero.
That is -3 + 4 + 5 -2 -4 = 0

Another example for the pair of 5s. i=4, j=7 -> [4,6] sums up to zero: -2 -4 + 6 = 0

that trick works for each input?

Algoman1 schrieb:

that trick works for each input?

Yes