Jan 6, 2009

Given an interger array of size n, how to find a subarray whose sum is equal to k. if there is, return 1, else 0. e.g. array[n]={1, 3, -4, 8, -1}

Given an interger array of size n, how to find a subarray whose sum is equal to k. if there is, return 1, else 0.
e.g. array[n]={1, 3, -4, 8, -1} k=10
because 3+8-1=10, then return 1;
What is the best time complexity??

Create the prefix sum array b[j]=b[j-1]+a[j] where j is from 0 O(n)
For each value in array b just try to find another value val where val-b[i]=k use hash table O(n)
For this condition, subarray (contiguous) like minimum subarray or specific subarray, we can take advantage prefix sum array
If you get the idx for Prefix sum array is from i to j
The subarray is from i+1 to j

No comments:

Post a Comment