LeetCode 1 Two Sum

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example

解题思路

刚开始感觉遍历所有两个元素的组合来判断是否等于目标值,需要n∗(n−1)/2 步。(O(n^2))

第一次尝试

测试

看起来这种方法应该符合条件,但其实不符合题目,题目说每个元素只能用一次,很明显第一种方法不符合题目(每个元素用了n-1次)

第二次尝试

题目要求每个元素只能用一次,那就意味着大O是O(n). 什么样的的算法可以遍历一遍所有元素判断出来呢?虽然,我想到了应该用map(hash table) 来写,但我对map不熟,看到别人的算法才明白该怎么做。

测试

这道题的解题关键是对hash table有很好的理解,切入点是每个元素只能用一次 ===> O(n). O(n) 意味着只能用一次for循环和大O是常数的算法,也只剩下hash table 能做到O(1)的search了。