Khuong - 1 year ago 74

Swift Question

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

}

For example:

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

But the complexity of this algorithm is

Is there any way faster.

Any helps would be appreciated. Thanks.

Answer Source

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
}
```