让我们一起啃算法----两数之和

前言

工作一段时间之后，最大的感觉就是算法好像没什么用，确实不会算法也能胜任平常的工作，但是总觉得缺了点什么，所以最近抽空复习了以前刷的 Leetcode，希望在这里找到一群志同道合的人。

两数之和（Two Sum）

这是 LeetCode 的第一题，总体来说是比较简单的，题干如下：

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那两个整数，并返回他们的数组下标。
示例:
    给定 nums = [2, 7, 11, 15]，target = 9
    因为 nums[0] + nums[1] = 2 + 7 = 9
    所以返回 [0, 1]
来源：力扣

简单来说就是给定一个数组，让你找到和为 target 的两个元素的索引。

解题思路

主要有 两种解题思路 ：

• 暴力解法：两层循环，外部循环的当前值与target的差值为内层循环需要定位的值。时间复杂度O(n^2)，空间复杂度O(1)。
• 优雅解法：一层循环，引入map，循环的当前值与target的差值在map中查找，如果不存在则将当前值作为键放入map，值的索引作为map的值，存在就返回。时间复杂度O(n)，空间复杂度O(n)。相比于暴力解法其实就是空间换时间。

代码实现

暴力解法GO实现：

/*暴力解法
思路：
    两层循环，外部循环的当前值与target的差值为内层循环需要定位的值
*/
func twoSumForce(nums []int, target int) (result []int) {
    length := len(nums)
    if length <= 0 {
        return
    }
    for i := 0; i < length; i++ {
        for j := i + 1; j < length; j++ {
            // 找到了就直接返回
            if nums[j] + nums[i] == target {
                return []int{i,j}
            }
        }
    }
    return
}

优雅解法GO实现：

/*优雅解法
思路：
    一层循环，引入map，循环的当前值与target的差值在map中查找，如果不存在则将当前值作为键放入map，值的索引作为map的值。
*/
func twoSumElegant(nums []int, target int) (result []int) {
    if len(nums) <= 0 {
        return
    }
    var m = make(map[int]int)
    for index, value := range nums {
        if v, ok := m[target-value]; !ok {
            // 将当前值和索引放入map中
            m[value] = index
        } else {
            return []int{index,v}
        }
    }
    return
}

总结

每天进步一点点，加油！
算法教程项目，每天更新一题，点个 star 支持一下呀：
https://github.com/wx-satellite/learning-algorithm

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