Describe a Θ(nlgn) time algorithm that, given a set S of n integers and another integer x, determines whether or not there exist two elements in S whose sum is exactly x.
func pairOf(sum:Int, in array:inout [Int]) throws -> (Int, Int)? {
guard array.count>1 else { throw TestError.argumentFault }
mergeSort(array: &array)
var low = 0, high = array.count-1
while low != high {
var currentSum = array[low] + array[high]
if currentSum > sum { high -= 1 }
else if currentSum < sum { low += 1 }
else { return (array[low], array[high]) }
}
return nil
}
var s = try Int.randomArray()
let sum = try Int.random()
try pairOf(sum: sum, in: &s)
网友评论