两数之和

描述

题目来源，https://leetcode-cn.com/problems/two-sum

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

假设每种输入只会对应一个答案。但同一个元素不能使用两次。

示例:

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

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

Go 语言实现

双重遍历

思路双重遍历确认两个数之和为 target 即可。注意第二个数从第一个数的后面元素遍历即可。

func TwoSum1(nums []int, target int) []int {
    // # 双重遍历
    //O(n^2), O(1)
    l := len(nums)
    for i, a := range nums {
        // 计算 当前元素和后续元素的和进行比较
        for j:=i+1; j<l; j++ {
            if a + nums[j] == target {
                return []int{i, j}
            }
        }
    }
    return []int {}
}

使用 map 存储补数

补数：若 a + b = target，那么在 target 下 a 和 b 互为补数。

思路，使用 map 结构，存储 key 为遍历值的 补数，而值对应值的索引。遍历时，判断是否存在该数的补数，若存在，找到答案！

func TwoSum2(nums []int, target int) []int {
    // # map 结构，在 map 中保存 补数 进行测试
    // O(N), O(N)
    vIdx := map[int]int{}
    for i, n := range nums {
        // 判断 n 的补数是否存在
        if idx, exists := vIdx[n]; exists {
            if i < idx {
                return []int {i, idx}
            } else {
                return []int {idx, i}
            }
        }
        // 以补数作为 key 存储补数及对应的索引
        vIdx[target - n] = i
    }
    return []int {}
}

本题来自于 Leetcode，在提交中表现如下：
执行用时 :4 ms, 在所有 golang 提交中击败了97.39%的用户
内存消耗 :3.7 MB, 在所有 golang 提交中击败了45.21%的用户

更多内容请访问或关注 红牛慕课， 红牛慕课

有疑问加站长微信联系（非本文作者）