1. Two Sum

[Problem]

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

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

You can return the answer in any order.

 

Example 1:

Input: nums = [2,7,11,15], target = 9

Output: [0,1]

Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

Example 2:

Input: nums = [3,2,4], target = 6

Output: [1,2]

Example 3:

Input: nums = [3,3], target = 6

Output: [0,1]

 

Constraints:

• 2 <= nums.length <= 104
• -109 <= nums[i] <= 109
• -109 <= target <= 109
• Only one valid answer exists.

[Solution]

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        dict = {}
        for idx, val in enumerate(nums):
            if target - val in dict:
                return [dict[target - val], idx]
            dict[val] = idx

 

Each element in array has to find out their pair that is equal to the value of subtracting themselves from "target". There can be two situations for each element of existing their pair.

 

1.  The pair element precedes themselves in the array.

2. The pair element is further behind themselves in the array.

 

I used hash table to storing index of pair element. I put {array index, array value} into hash table while iterating over the nums array. 

 

1. If there is already their pair element in hash table, just return [pair element's index,  current index]

2. if not, put {current index, current value} into hash table

 

https://leetcode.com/problems/two-sum/