Here is an O(n*n) time complexity solution with O(n*n) space cost.
The basic idea is using double hashing(hash+set):
Step 1:
Use two for loops to calculate the sum of two integers and store them
in the hash table, which also has an inner set storing the two
integers' index.
E.g. For array {100,200,300} the hash looks like:
,
<100+200, <0, 1>>
<100+300, <0, 2>>
<200+300, <1, 2>>
Step 2:
Use two for loops again to calculate sum of two integers, we called S.
Try to check the above hash whether there is an item with the value K-S
and no intersection with the inner set.
Sent from my Windows Phone
发件人: SAMMM
发送时间: 2012/1/2 1:34
收件人: Algorithm Geeks
主题: [algogeeks] Sum of Four Numbers in an Array (Amazon)
Given an array A[] and a integer num(K) . Need to find the combination
of four no's in the array whose sum is equal to num(K).
--
You received this message because you are subscribed to the Google
Groups "Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
