算法-两数相加TwoSum

两数相加问题

假设存在一个整数数组，[2,5,7,10,33,23]。 数组里面的数无序但可保证不重复。给定一个目标值C，例如9. 尝试找出数组中所有满足A+B=C的元素，最终输出A和B的数组下标。

例如: 2+7=9 则最终输出[0,2]。 0和2分别对应2，7的下标。

方案一 轮询法

使用两个for循环依次查找。 从第一个元素i开始，如果小于C，则使用第二个for循环查找C-i。 如果找到则返回，如果没找到，则继续第二轮查找。

package main

import "fmt"

func main() {  
    arr := []int{2, 7, 5, 10, 22, 34, 20,}

    target := 12

    var result []int
    for i, a := range arr {
        if a < target {
            for n, b := range arr[i+1:] {
                if b == target-a {
                    result = []int{i, n + i + 1}
                    break
                }
            }
        }
    }

    fmt.Println(result)
}

方案二 两阶段MAP方案

方案一的时间算法复杂度是N的平方(本人的Markdown编辑器不支持latex, 所以只能写汉字了..)，而空间复杂度则是N。可以借助两个map，将一层for循环去掉。

package main

import "fmt"

func main() {  
    arr := []int{2, 7, 5, 10, 22, 34, 20,}

    target := 12

    fmt.Println(towPassMap(arr, target))
}

func towPassMap(arr []int, c int) (result []int) {  
    m := make(map[int]int)

    for i, a := range arr {
        m[a] = i
    }

    for i, a := range arr {
        if _, ok := m[c-a]; ok {
            result = []int{i, m[c-a]}
            return
        }
    }
    return
}

方案三 一阶段MAP方案

借助一个Map之后，时间复杂度降为了N。而空间复杂度仍然为N。 其实上面的算法并非最优算法，我们还可以再进行优化，也就是仅使用一次MAP。

package main

import "fmt"

func main() {  
    arr := []int{2, 7, 5, 10, 22, 34, 20,}

    target := 12

    fmt.Println(onePassMap(arr, target))
}

func onePassMap(arr []int, c int) (result []int) {  
    m := make(map[int]int)

    for i, a := range arr {
        m[a] = i
        if a > c {
            continue
        }

        if _, ok := m[c-a]; ok {
            return []int{i, m[c-a]}
        }

    }

    return
}

因为只存在一个for循环，所以时间复杂度仍然为N，但同方案二相比，减少了元素遍历次数，只有在最差情况下，匹配效率才和方案二相同。