给定一个整数数组,如果两个元素值之和等于给定的值,则返回它们的索引。
你可以假定只有一个明确的答案,而且不能使用同一元素两次。

原题

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

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

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

分析

  • 目标:两元素的索引
  • 依据:两元素的值之和与给定的值是否相等

实现

双重循环

按照题意,脑海最开始浮现的解法是用双重循环,将每个元素和其他元素相加,判断是否和给定值相等即可,相等则返回结束,否则继续。

 1func twoSum(nums []int, target int) []int {
 2    for i := 0; i < len(nums); i++ {
 3        for j := i + 1; j < len(nums); j++ {
 4            if nums[i]+nums[j] == target {
 5                return []int{i, j}
 6            }
 7        }
 8    }
 9
10    return []int{}
11}

Map

但是双重循环的时间复杂度是 O(n^2),是否有更好的解法呢? 是否可以使用 Map 呢?如何使用呢?

根据之前的分析,换个角度看,依据可以理解为:给定值和元素之间的差值,那么用 Map 来存储 ‘数值’ => ‘索引’ 的映射的话,则问题迎刃而解。

 1func twoSum(nums []int, target int) []int {
 2    m := map[int]int{}
 3    for i := 0; i < len(nums); i++ {
 4        m[nums[i]] = i
 5    }
 6
 7    for i := 0; i < len(nums); i++ {
 8        minus := target - nums[i]
 9        if j, ok := m[minus]; ok && i != j {
10            return []int{i, j}
11        }
12    }
13
14    return []int{}
15}

Map 改良版

上面的 Map 解法的使得时间复杂度从 O(n^2) 将为 O(n),确切来说是2*O(n),因为额外用了一个循环,将整数和其索引的映射存储到 Map 中,如果将两个循环合并在一起呢?

仔细思考了下,于是得出以下优化后的代码,其中 m[nums[i]] = i 放在判断后面,可以避免多次使用同一元素。

 1func twoSum(nums []int, target int) []int {
 2    m := map[int]int{}
 3
 4    for i := 0; i < len(nums); i++ {
 5        minus := target - nums[i]
 6        if j, ok := m[minus]; ok {
 7            return []int{i, j}
 8        }
 9
10        // the code placed here can avoid using the same element twice.
11        m[nums[i]] = i
12    }
13
14    return []int{}
15}