两数之和

题目来源

题目传送门

解题思路

方法一：暴力破解

个人解

关键点：用两层循环进行解题

代码实现

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        result = []
        loop = False
        for i, num in enumerate(nums):
            for j, v in enumerate(nums):
                if i != j:
                    if num + v == target:
                        result.append(i)
                        result.append(j)
                        loop = True
                        break
            if loop:
                break
        return result

func twoSum(nums []int, target int) []int {
    resultSlice := make([]int, 0, 2)
    Loop:
    // 1. 循环遍历 nums
    for i, num := range nums {
        // 2. 循环遍历 nums
        for j, v := range nums {
            // 3. 判断元素是否重复
            if i != j {
                // 4. 两数之和等于目标值
                if num + v == target {
                    resultSlice = append(resultSlice, i)
                    resultSlice = append(resultSlice, j)
                    break Loop
                }
            }
        }
    }
    return resultSlice
}

个人总结：
- Python3 版本提交结果 ✅ ，执行用时 6524 ms，内存消耗 15.5 MB。
- Golang 版本提交结果 ✅ ，执行用时 48 ms，内存消耗 3.4 MB。
- 可改进点：第二次遍历的时候，应该从 i + 1 元素开始。

官方解

关键点：
- 最容易想到的方法是枚举数组中的每一个数 x ，寻找数组中是否存在 target - x 。
- 当我们使用遍历整个数组的方式寻找 target - x 时，需要注意到每一个位于 x 之前的元素都已经和 x 匹配过，因此不需要再进行匹配。
- 而每一个元素不能被使用两次，所以我们只需要在 x 后面的元素中寻找 target - x 。

代码实现

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        n = len(nums)
        for i in range(n):
            for j in range(i + 1, n):
                if nums[i] + nums[j] == target:
                    return [i, j]
        return []

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)，其中 N 是数组中的元素数量。最坏情况下数组中任意两个数都要被匹配一次。
- 空间复杂度：O(1)。

方法二：哈希表

个人解

关键点：用哈希表进行解题

代码实现

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        records = dict()
        # 用枚举更方便，就不需要通过索引再去取当前位置的值
        for idx, val in enumerate(nums):
            if target - val not in records:
                records[val] = idx
            else:
                return [records[target - val], idx] # 如果存在就返回字典记录索引和当前索引

func twoSum(nums []int, target int) []int {
    resultSlice := make([]int, 0, 2)
    sliceMap := make(map[int]int)
    for i, num := range nums {
        sliceMap[num] = i
    }
    for j, v := range nums {
        if _, ok := sliceMap[target - v]; ok {
            if j == sliceMap[target - v] {
                continue
            }
            resultSlice = append(resultSlice, j)
            resultSlice = append(resultSlice, sliceMap[target - v])
            break
        } 
        continue
    }
    return resultSlice
}

个人总结：
- Python3 版本提交结果 ✅ ，执行用时 28 ms，内存消耗 16 MB。
- Golang 版本提交结果 ✅ ，执行用时 8 ms，内存消耗 5.4 MB。
- 可改进点：哈希表添加元素和匹配可以同时进行。

官方解

关键点：
- 注意到方法一的时间复杂度较高的原因是寻找 target - x 的时间复杂度过高。
- 因此，我们需要一种更优秀的方法，能够快速寻找数组中是否存在目标元素。如果存在，我们需要找出它的索引。
- 使用哈希表，可以将寻找 target - x 的时间复杂度降低到从 O(N^2) 降低到 O(1)。
- 这样我们创建一个哈希表，对于每一个 x ，我们首先查询哈希表中是否存在 target - x ，然后将 x 插入到哈希表中，即可保证不会让 x 和自己匹配。

代码实现

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        hashtable = dict()
        for i, num in enumerate(nums):
            if target - num in hashtable:
                return [hashtable[target - num], i]
            hashtable[nums[i]] = i
        return []

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)，其中 N 是数组中的元素数量。对于每一个元素 x ，我们可以 O(1) 地寻找 target - x 。
- 空间复杂度：O(N)，其中 N 是数组中的元素数量。主要为哈希表的开销。