1 minute read

1. Two Sum

Difficulty: Easy

Related Topics: Array, Hash Table

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]

First Attempt:

Code:

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        for i in range(len(nums)):
            for j in range(len(nums)):
                if i!=j:
                    if nums[i] + nums[j] == target:
                        return [i,j]

Feedbacks:

Horrible code. Need to fix time complexity O(n^2) to O(n)

Second Attempt:

Code:

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        checked = {}
        i = 0
        while target - nums[i] not in checked:
            checked[nums[i]] = i
            i+=1
        return [checked[target - nums[i]],i]

Feedbacks:

HashTable can be used in python by dictionary. Using dictionary, this problem could be solved by time complexity of O(n). Need to work on data structures also.

You may also enjoy