[Leetcode] Two Sum

Problem

Given an array of integers, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.

You may assume that each input would have exactly one solution.

Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2

Analysis

• 用一个hash表来围护每个数和其对应的index
• 如果有重复的数字，则overwrite， 即保留最后出现的index
• 然后遍历所有的数，如果 （target - 当前数）在哈希表中，且俩数的index不一样，则找到解了
• 复杂度
• Time: O(n)
• Space: O(n)

Code

Reference
[1] https://leetcode.com/problems/two-sum/