CareerCup

Are you sure that example is correct? 5-3-1+2-3 = 0, not 1.

Anyway, one possible solution is to maintain a HashSet of partial sums. Partial sum is defined as follows:
partial_sum[0] = 0
partial_sum[i] = input[0] + input[1] + ... + input[i-1]

Notice that in order to find a sub-array whose elements sum to a given number k, it would suffice to find 0<=i<j<=input.length such that:
k = partial_sum[j] - partial_sum[i] = input[i] + input[i+1] + ... + input[j-1]

This is equivalent to finding an index i<j given some j which satisfies:
partial_sum[i] = partial_sum[j] - k

Using this observation, iterate over the input array and maintain the following:
1. Current partial sum (partial_sum[i+1]) where i is the current index
2. A HashSet of the previous partial sums: hashset = {partial_sum[0], partial_sum[1],...,partial_sum[i]}. At the end of each iteration we add the current partial sum to the hashset.

During each iteration, check whether the hashset contains partial_sum[j+1]-k. If it does then all that's left is to find an appropriate index i such that:
partial_sum[i] = partial_sum[j+1] - k
and return the sub-array from i to j.

Notice the found i will satisfy i<=j because of (2) above.

Complexity: O(n) average run-time complexity with O(n) space complexity.

private static int getIndexForSum(int[] arr, int sum){
		if (arr==null){
			throw new NullPointerException("arr cannot be null");
		}
		
		int i=0;
		int curSum=0;
		for (;(curSum!=sum) && (i<arr.length);i++){curSum+=arr[i];}
		
		return i;
	}
	
	public static int[] findSubSet(int[] arr, int k){
		if (arr==null){
			throw new NullPointerException("arr cannot be null");
		}
		
		Set<Integer> sumsSet = new HashSet<Integer>();
		int sum = 0;
		sumsSet.add(sum);
		int start = -1;
		int end = -1;
		for (int i=0;i<arr.length;i++){
			sum+=arr[i];
			if (sumsSet.contains(sum-k)){
				start = getIndexForSum(arr,sum-k);
				end = i;
				break;
			}
			sumsSet.add(sum);
		}
		
		return (end!=-1) ? Arrays.copyOfRange(arr, start, end+1) : null;
		
	}

In the code above the k is the desired sub-array sum (in the original problem it should be 1)

Not sure if it's the best solution though, maybe someone can offer a worst case linear algorithm.

Typical DP problem, by the way, do you need the longest sequence, or anyone is fine. If no longest constraint, the python code below could solve the problem:

def sum_equal_k(A,k):
	results=[]	
	for i,v in enumerate(A):
		for idx in range(len(results)):
			results[idx][1]+=v
		results.append([i,v])
		for r in results:
			if r[1]==k:
				print(r,i)

sum_equal_k([4,3,5,-3,-1,2,-3,10,2],1)

stackoverflow.com<slash>questions<slash>5534063<slash>zero-sum-subarray

you could subtract 1 from all elements and search for the largest zero subarray :)

I guess it should be O(n), but i haven't coded it yet