0001._two_sum.md

Links:

1. https://leetcode.com/problems/two-sum/
2. https://leetcode-cn.com/problems/two-sum/

Key words:

1. Inverted index 反向索引
2. 空间换时间 by hash_table(dict)
3. enumerate 枚举

Tags

1. 哈希表
2. 数组

Solution:

1. 建立一个字典hash_table(空间换时间)， key为数字， value为数字的index. (反向索引)。

2. 枚举数字，假设当前枚举的数字为num，索引为index，目标数字为target。

3. 判断 if (target - num) in hash_table。

4. 如果存在， 则返回num的index和(target - num)的index。

5. 如果不存在，则将{ num: index }更新到hash_table。

6. 跳到第二步。

7. 如果不能再枚举，则证明找不到，返回None(Python如果没写return， 默认返回None)。

Python:

class Solution:
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        memo = {}

        for index, num in enumerate(nums):
            if target - num in memo:
                return [index, memo[target - num]]
            else:
                memo[num] = index

Go:

package main

func twoSum(nums []int, target int) []int {
	m := make(map[int]int)

	for idx, val := range nums {
		if idx2, ok := m[target-val]; ok {
			return []int{idx, idx2}
		}

		m[val] = idx
	}
	return 0
}