两数之和

@爱耍流氓的唐僧  November 27, 2020

给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是,数组中同一个元素不能使用两遍。

 

示例:

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

暴力法:

func twoSum(nums []int, target int) []int {
    for key,value := range nums{
        left := target - value
        for k,v := range nums{
            if(k == key){
                continue
            }
            if(v == left){
                 return []int{key,k}
            }
        }
    }
    return nil
}

时间复杂度:O(N^2)
空间复杂度:O(1)
Map法(Go的Map是Hash Map)
微信图片_20201127170001.png

func twoSum2(nums []int, target int) []int {
    m := map[int]int{}
    for i, v := range nums {
        if k, ok := m[target-v]; ok {
            return []int{k, i}
        }
        m[v] = i
    }
    return nil
}

时间复杂度:O(N)
空间复杂度:O(N)


添加新评论

  1. aprmay

    写的不错,继续关注楼主,多写出好文章,支持。。。

    Reply
    1. @aprmay

      谢谢,请多支持

      Reply