I guess this has already been discuss in this forum before. Anyways let me give my algo here. Let us assume that the array is sorted in ascending order WLOG.
let low=1 and high=n index the first and last elements
while(low<high)
{
if a[low]+a[high] == z, done, so break off
if a[low]+a[high]<z need to increase sum, so low++;
3rd case, u need to decrease, so high--
}
hope this helps.
-Vijay
On 12/19/05, Uppala Babu <[EMAIL PROTECTED]> wrote:
Hash map takes extra space if you want O(1) search..
Otherwise .. it takes time... any another solution...
in O(n) time with no extra space.. ;-)On 12/19/05, Hemanth < [EMAIL PROTECTED]> wrote:
This answer is something like a bit vector based one.
Assume that the array is int[] num.
for(int i = 0; i < num.length; i++)
{
int otherNum = z - num[i];
// Search in a hashmap we maintain for 'otherNum'
// if 'otherNum' is present, then we are done
// else add 'num[i]' to the hashmap and proceed
// to the next iteration.
}
