Leetcode 1. Two Sum in python

Question description:

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.

Let’s use the example below to illustrate:

nums = [2,7,11,15], target =9

Method 1: Array loop

We choose the way of selecting the two numbers from thenumsarray by using two indexes, i.e., the index i and j.

what are the ranges of index i and j? Since we have 4 numbers in nums , we need to consider all 4 numbers by iteration of the len(nums) .

Need to take note, not all numbers indexed by i and j can be used, to avoid the repeated answers, i<j is defined as shown in Fig.1 to limit the pairs indexed.

Fig 1. Illustration of the index in loop method.

Code:

def twosum(nums, target):
       for i in range(len(nums)): 
        for j in range(len(nums)): 
            if i<j: 
                add_ = nums[i] + nums[j] 
                #print('Sum is {}, i: {}, j: {}'.format(add_, i , j))
                if add_ == target:
                    return [i,j]
                                       
    return result

Method 2: Dictionary lookup

This method is not so direct as the array looping. The key idea is to store the delta between the target and the looked up number as the keys of the dict and the location of the numbers are stored as the value in dict . Once the indexed number from the array is found in the previously stored keys, the pair is found. The methodology is illustrated in Fig.2 below.

Code:

def twoSum(nums, target):
    add_ = {}
    for i in range(len(nums)):
        n = nums[i]
        if n in add_: 
            #print('Found n: {} in the dict:{}'.format(n, add_))
            return [add_[n], i]
        else:
            add_[target-n] = i 
            print('add_: {}'.format(add_))
    return []

Fig.2 Dictionary lookup of the targeted pair.

Thanks for reading :)