check sum

Problem

Given array of sorted number, check if there are any two numbers in the array can have the sum provided source

Solution

第一种解法利用到了题目中说的数组是从小到大排列的顺序,拿头尾相加作为初始状态,然后与sum比较,如果大于则尾部往前推,反之则头部往后走。

func checkSum(arr: [Int], sum: Int) -> Bool {  
    var head = 0
    var tail = arr.count - 1
    while head < tail {
        let theSum = arr[head] + arr[tail]
        if theSum == sum {
            return true
        }
        else if theSum < sum {
            head += 1
        }
        else {
            tail -= 1
        }
    }

    return false
}

let resul1 = checkSum(arr: [1,2,3,9], sum: 8)  
let resul2 = checkSum(arr: [1,2,4,4], sum: 8)  

进化

如果数组不能保证是排好序的,则要怎么算 可以利用dictionary来存储iterate过的数,只是这里key用当时iterate的数的complementary (sum - value),这样只要在后面的数组中找出有没有相应的key即可。

func checkSum(arr: [Int], sum: Int) -> Bool {  
    var dict = [Int: Bool]()
    for item in arr {
        if let _ = dict[item] {
            return true
        }
        dict[sum - item] = true
    }

    return false
}

let resul1 = checkSum(arr: [1,2,3,9], sum: 8)  
let resul2 = checkSum(arr: [1,2,4,4], sum: 8)