Golang算法之两数之和

发表于 | 更新于 | 分类于 | 浏览数
| 字数统计 678

两数之和，简单难度，leetcode地址：https://leetcode-cn.com/problems/two-sum

1.描述

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出和为目标值 target 的那两个整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。 你可以按任意顺序返回答案。

示例 1：

1
2
3
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1]

示例 2：

1
2
输入：nums = [3,2,4], target = 6
输出：[1,2]

2.题解

方法一: 双重遍历循环

大多数人第一时间想到的方法就是这个，即使没有了解过复杂算法的人应该也能写出来，也有人称之为暴力枚举法，之所以说是暴力，指的是其时间复杂度达到了N2，换句话说费CPU。

但是也不是一无是处，至少人家省内存，空间复杂度是1

代码逻辑很简单，朴实无华，2层for循环嵌套就可以做到，需要注意的是内层循环可以从外层+1开始，可以少循环几次

参考代码:

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

方法二：哈希表

了解过哈希表这种数据结构应该知道，其查询速度非常块，时间复杂度最好的情况下可以达到1，我们可以利用这点优化上面的算法。

首先，我们初始化一个哈希表，以示例1为例，第一个数2和目标值9的差值是7，这时候我们从哈希表里面寻找这个值，第一次当然找不到，那么我们就把2作为key放进哈希表，value就是当前下标0

第二次循环的时候，7和9的差值是2，这时候再从哈希表里面查找就会发现刚好有一个key为2的元素，刚好就是我们想要的结果。

这种算法时间复杂度是N，因为只需要循环一次，但是空间复杂度从1变成N，说白了，比较费内存。

参考代码:

1
2
3
4
5
6
7
8
9
10
11
12
func twoSum(nums []int, target int) []int {
    m := make(map[int]int) // 在go里面，map数据结构就是哈希表的一种实现
    for i := 0; i < len(nums); i++ {
        dif := target - nums[i]
        if j, ok := m[dif]; ok {
            return []int{j, i}
        } else {
            m[nums[i]] = i
        }
    }
    return nil
}