Day 28：1. Two Sum

今日题目

题目连结：1. Two Sum
题目主题：Array, Hash Table

简单说说 Hash Table

Hash Table 主要的核心概念是使用 Key 去快速找到需要的 Value，而这个 Key 是用资料经过计算之後得到的值，通常是用 Hash Function 来得到一个值来当作 Key。

另外 Hash Table 也可以当作分类的方式来使用，前一篇有提到 Hash Functioin 要小心碰撞 (Collision) 的问题，但在这边是刻意使用 Collision 来当作分类使用，下面是一个 Hash Table 用姓氏当范例：

这边可以看到，是用姓氏的第一个字来当做 Key ，当中如果 Value 有多个的状况是因爲出现碰撞的况状，所以分类到同一个 Key 里面。搜寻时也只要拿姓氏的第一个英文字母，就可以很快的搜寻到目标是否有在这个表里面。

题目解说

建议可以看看LeetCode原本的题目说明，这边是用我的方式说明题目，参考就好。

题目会给一个 nums 数字阵列及一个 target 目标值，目的是要在 nums 之中找到可以相加成 target 的两个数字，最终回传这两个数字的位置。

可以假设在答案一定只有一个的情况下去找出这两个数字，另外 nums 中一个值只能使用一次。

约束：

• 2 <= nums.length <= 10的4次方
• -10的9次方 <= nums[i] <= 10的9次方
• -10的9次方 <= target <= 10的9次方
• 只会有一个答案在 nums 中

范例1

输入: nums = [2,7,11,15], target = 9
输出: [0,1]
解说: nums[0]是2, nums[1]是7， 2 + 7 = 9，最後输出[0, 1].

范例2

输入: nums = [3,2,4], target = 6
输出: [1,2]
解说: nums[1]是2, nums[2]是4， 2 + 4 = 6，最後输出[1, 2].

范例3

输入: nums = [3,3], target = 6
输出: [0,1]
解说: nums[0]是3, nums[1]是3， 3 + 3 = 6，最後输出[0, 1].

建议到这边先停下来，尝试自己解解看，若没有想法可再继续走下去。

解题的想像

文字描述

1. 宣告一个 map 来实作 Hash Table。
2. 跑一个回圈，每一圈处理的内容有：
   • 确认目前的数字是否有在map的key中，若有出现代表找到可加总成target的两个数字位置，直接回传这两个位置结束。
   • 将（taget - 目前的数字）当作是map的key，位置(index)当value。

图解过程

范例： nums = [2, 11, 15, 8, 4], target = 10

上图是回圈在跑的过程，下方的圆角长方是一个Hash Table，每一圈都会拿一个数字来确认是否有出现在 Hash Table 中。

step1 ~ step3 是没有出现在 Hash Table 的状况，所以会将 target - 目前的数字当作 key，位置（index）当 value。

step4 的 8 有在 Hash Table 中找到，代表有找到两个数字加起来等於 taget 的两个位置，最後将回传这个 value 0 及目前的位置 3 结束。

若因为没想法而走到这边，建议看完想像以後再给自己一次机会试一次。

程序码撰写

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        # Hash Table
        map = {}
        for i in range(len(nums)):
            # 若目前的数字已经进到 map 
            # 代表找到可加总成target的两个数字位置
            if nums[i] in map:
                return [map[nums[i]], i]
            # 将（taget - 目前的数字）当作是map的key，位置当value
            key = target - nums[i]
            map[key] = i

希望您今天能了解到...

1. Hash Table 的基本概念
2. 1. Two Sum 的解题方法

若内容有什麽问题或建议欢迎一起交流：）
感谢您今天愿意花时间看完这篇文章~~~~

Next：653. Two Sum IV - Input is a BST