[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:
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.

Logic

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.

Code

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
Subscribe
Notify of
guest
0 Comments
Inline Feedbacks
View all comments