Khuong - 1 year ago 74
Swift Question

# Find the pair in array with condition

Let say I have an array of Int, I want to find a pair of number in this array that the sum of this pair is equal to an number, like so:

``````func findPair(list: [Int], _ sum: Int) -> (Int, Int)? {
for i in 0..<list.count - 1{
for j in (i+1)..<list.count {
let sumOfPair = list[i] + list[j]
if sumOfPair == sum {
return (list[i], list[j])
}
}
}
return nil
}
``````

The first parameter is an array of Int, the second parameter is an number that we need to compare some pairs in that array.

For example:

``````findPair([1,2,3,4,5], 7) // will return (2, 5), because 2 + 5 = 7
``````

But the complexity of this algorithm is O(n^2).

Is there any way faster.

Any helps would be appreciated. Thanks.

Try with this:

``````func findPair(list: [Int], _ sum: Int) -> (Int, Int)? {
//save list of value of sum - item.
var hash = Set<Int>()
var dictCount = [Int: Int]()
for item in list {

//keep track of count of each element to avoid problem: [2, 3, 5], 10 -> result = (5,5)
if (!dictCount.keys.contains(item)) {
dictCount[item] = 1
} else {
dictCount[item] = dictCount[item]! + 1
}
//if my hash does not contain the (sum - item) value -> insert to hash.
if !hash.contains(sum-item) {
hash.insert(sum-item)
}

//check if current item is the same as another hash value or not, if yes, return the tuple.
if hash.contains(item) &&
(dictCount[item] > 1 || sum != item*2) // check if we have 5+5 = 10 or not.
{
return (item, sum-item)
}
}
return nil
}
``````