3-sum problem to be optimized
Jimmy
posted @ 2011年12月21日 13:53
in Others
, 2179 阅读
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?
2011年12月21日 20:35
用map存所有的2-sum,再扫一遍看m-i在map里是否存在?