1 Two Sum - Easy

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.

Follow-up: Can you come up with an algorithm that is less than O(n2) time complexity?

Problem Analysis:

initialize a dictionary to keep track of value:index pair, since the output we want is the indexes of suitable values
at the second pass, check if the diff is already in the dictionary. if yes, a suitable solution is found. else continue finding

Solutions:

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        map = {} # value:index

        for i, n in enumerate(nums):
            diff = target - n
            if diff in map:
                return [map[diff], i]
            map[n] = i
            
        return

Walter Teng.

1 Two Sum - Easy

Problem:

Problem Analysis:

Solutions:

Similar Questions