首页 > 其他 > 详细

Leetcode_1.Two Sum

时间:2018-06-18 23:08:28      阅读:236      评论:0      收藏:0      [点我收藏+]

1. Two Sum

  • 输入:一个整数数组nums[],一个整数target
  • 返回:数组中找出2个数,使其和为target,并返回两个数在数列中的索引。

比如:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

思路:

遍历数组,并将数组元素(键值对,nums[i]:i)加入HashMap中,对于每个元素nums[i],在哈希表中查找是否存在target-nums[i],找出对应的元素,返回元素index。时间复杂度为O(n),空间复杂度O(n)。

func twoSum(nums []int, target int) []int {
    m := make(map[int]int)    
    for i:=0; i<len(nums); i++{
        another := target - nums[i]
        
        if _, ok := m[another]; ok{
            return []int{m[another], i}
        }        
        m[nums[i]] = i
    }    
    return nil
}

for循环部分可以使用range,两者没有明显差异

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

Leetcode_1.Two Sum

原文:https://www.cnblogs.com/gexin/p/9196617.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!