Matrix Algorithm in linear time
xshell Error: Unable to initialize gtk, is DISPLAY set properly?

3-sum problem to be optimized

Jimmy posted @ 2011年12月21日 13:53 in Others , 2119 阅读

Problem Description: Given an array A[1...n] consisting of integers and an integer m. Find three elements in A, so that sum of the three integers in A equals to m. 

Algorithm I:
for i from 1 to n-2
    do for j from i+1 to n-1
        do for k from j+1 to n
            do if A[i] + A[j] + A[k] = m
                   then print A[i], A[j], A[k]
Time complexity of this algorithm is O(n^3)
 
Algorithm II:
sort array A
for i from 1 to n-2
    do for j from i+1 to n-1
        do binary_search(A[j+1...n], m-A[i]-[j])
Time complexity of this algorithm is O(n^2logn)
 
We now want to optimize the problem to have a solution of time complexity O(n^2).
 
PS: Prof. Kao gave this problem in class, and he said no one fixed it out in the previous final exam. Do you have some ideas?
Avatar_small
scturtle 说:
2011年12月21日 20:35

用map存所有的2-sum,再扫一遍看m-i在map里是否存在?


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter