算法-两数相加TwoSum

栏目: 编程工具 · 发布时间: 7年前

内容简介:假设存在一个整数数组,[2,5,7,10,33,23]。 数组里面的数无序但可保证不重复。给定一个目标值C,例如9. 尝试找出数组中所有满足A+B=C的元素,最终输出A和B的数组下标。例如:使用两个for循环依次查找。 从第一个元素i开始,如果小于C,则使用第二个for循环查找C-i。 如果找到则返回,如果没找到,则继续第二轮查找。

两数相加问题

假设存在一个整数数组,[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,但同方案二相比,减少了元素遍历次数,只有在最差情况下,匹配效率才和方案二相同。


以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

Programming Python

Programming Python

Mark Lutz / O'Reilly Media / 2006-8-30 / USD 59.99

Already the industry standard for Python users, "Programming Python" from O'Reilly just got even better. This third edition has been updated to reflect current best practices and the abundance of chan......一起来看看 《Programming Python》 这本书的介绍吧!

Base64 编码/解码
Base64 编码/解码

Base64 编码/解码

XML、JSON 在线转换
XML、JSON 在线转换

在线XML、JSON转换工具

HEX HSV 转换工具
HEX HSV 转换工具

HEX HSV 互换工具