[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.
Given nums = [2, 7, 11, 15], target = 9, Because nums[0] + nums[1] = 2 + 7 = 9, return [0, 1].

This is the first question in Leetcode, and it’s more inspiring than I thought when I saw its echo in two recent contest questions: [Leetcode]1498. Number of Subsequences That Satisfy the Given Sum Condition and [Leetcode]1497. Check If Array Pairs Are Divisible by k. Therefore I’d like to share it here and let’s see how to use hashmap to improve the time complexity.


The brute force approach would be scanning nums looking for the partner for each number, which results in O(n^2). To achieve O(n) time complexity, we can use a hashmap to store the number that we have scanned, and when we find target-current has been scanned, we can return it.


class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        dic = {}
        for i,val in enumerate(nums):
            if target-val in dic:
                return [dic[target-val],i]
            # if not found, store the value-index in the hashmap
            dic[val] = i
Notify of
Inline Feedbacks
View all comments