DEV Community

HHMathewChan
HHMathewChan

Posted on • Originally published at rebirthwithcode.tech

Python Exercise 23: Two sum

#python #beginners #leetcode

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
Enter fullscreen mode Exit fullscreen mode
  • 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]
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode
  • 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]
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode
  • 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
Enter fullscreen mode Exit fullscreen mode

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

Top comments (0)