算法练习第一天——两数之和

算法练习第一天——两数之和

两数之和题目

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

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

示例1：

输入：nums = [1,2,5,7,8], target = 9

输出：[0,3]和[2,4]

解释：因为 nums[0] + nums[3] == 9 ，返回 [0,3]，nums[2]+nums[4] == 9，返回 [2,4]。

示例2：

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

输出： [0,2]

示例3：

输入： nums = [2,2], target = 4

输出： [0,1]

解题思路

方法一：暴力枚举

枚举数组中的每一个数x，寻找数组中是否有一个数为targrt-x，当我们在遍历寻找target-x时X前的每一个元素都已近和X匹配过，而每一个元素不能被使用两次，因此在遍历时只要在X后取寻找target-x这个数字。

代码以golang为例子：

func twoSum(nums []int, target int) []int {
    for i, x := range nums {
        for j := i + 1; j < len(nums); j++ {
            if x+nums[j] == target {
                return []int{i, j}
            }
        }
    }
    return nil
}

该解法复杂度

• 时间复杂度：O(N^2)O(N2)，其中 NN 是数组中的元素数量。最坏情况下数组中任意两个数都要被匹配一次。
• 空间复杂度：O(1)O(1)。

方法二：哈希表

我们创建一个哈希表，对于每一个 x，我们首先查询哈希表中是否存在 target - x，然后将 x 插入到哈希表中，即可保证不会让 x 和自己匹配。

func twoSum(nums []int, target int) []int {
    hashTable := map[int]int{}
    for i, x := range nums {
        if p, ok := hashTable[target-x]; ok {
            return []int{p, i}
        }
        hashTable[x] = i
    }
    return nil
}

该解法复杂度

• 时间复杂度：O(N)。
• 空间复杂度：O(N)。