Two sum#

Levels: level-0

Data structures: array, hash-table

Practice Link#

Description#

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.

Python Solution#

 1class Solution1(object):
 2    def twoSum(self, nums, target):
 3        """
 4        :type nums: List[int]
 5        :type target: int
 6        :rtype: List[int]
 7        nlog(n) complexity using sorting. 
 8        """
 9        nums.sort()
10        l = len(nums)
11        start = 0
12        end = l - 1
13        while start < end:
14            s = nums[start] + nums[end]
15            if s == target:
16                return [start, end]
17            if s > target:
18                end -= 1
19                continue
20            start += 1
21        return []
22
23
24class Solution2(object):
25    def twoSum(self, nums, target):
26        """
27        :type nums: List[int]
28        :type target: int
29        :rtype: List[int]
30        O(n) complexity using hashmap. 
31        """
32        m = {}
33        for idx, num in enumerate(nums):
34            complement = target - num
35            if complement in m:
36                return [idx, m[complement]]
37            m[num] = idx
38        return []
39
40
41if __name__ == "__main__":
42    nin = [2, 1, 2, 1, 0, 1, 2]
43    tin = 3
44    #p = [3,3,5,0,0,3,1,4]
45    sol = Solution2()
46    r = sol.twoSum(nin, tin)
47    print(r)