## DEV Community

HHMathewChan

Posted on • Originally published at rebirthwithcode.tech

# Python Exercise 23: Two sum

## Question

• 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

• 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]

### Constraints:

• `2 <= nums.length <= 104`
• `-109 <= nums[i] <= 109`
• `-109 <= target <= 109`
• Only one valid answer exists.

## My attempt

### First attempt

• The algorithm is work theoretical but too slow, run out of time if last two test case
• algorithm
``````> find the indices of the two number such that they add up to target
>>find two number if they add up to the target
for index1, num1 in the nums:
for index2,num2 in the nums:
if num2 is not the same number as num1:
if value1 + value 2 == target:
return a list consist of index1 and index2
``````
• code
``````class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
final_list = [[index1,index2] for index1,value1 in enumerate(nums) for index2,value2 in enumerate(nums) if index2 > index1 if value1+value2 ==target]
return final_list[0]

``````

### Second attempt (success pass all test)

• algorithm
``````> find the indices of the two number such that they add up to target
>>find two number if they add up to the target
for index1,value1 in nums:
calculate a second_number that have a sum with value equals to target
if second is in nums:
find the indices of the second_number
if the second_number is not the same number as value1:
return a list consist of index1 and index2
``````
• code
``````class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
for index1, value1 in enumerate(nums):
second_number = target - value1
if second_number in nums:
second_number_index = nums.index(second_number)
if second_number_index != index1:
return [index1, second_number_index]
``````

## Other solution

### Claim to be the fastest algorithm with 0(n) complexity

• algorithm
``````> find the indices of the two number such that they add up to target
initiate seen as empty dictionary
for index, value in nums:
calculate a second_number that have a sum with value equals to target
if second_number is in seen dictionary:
return a list of index and the index of second_number
if second_number is not in seen:
add the value as key and index as value in the seen dictionary
``````
• code
``````class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
seen = {}
for index, value in enumerate(nums):
second_number = target - value

if remaining in seen:
return [index, seen[second_number]]

seen[value] = index
``````

## My reflection

This is a good challenge to make me think a method that not just rely on for loop completely. And I learn a new pattern form others to use a dictionary to reduce searching time.

## Credit

challenge on leetcode 1
solution on code recipe