Question

Given an array of integers
nums
and an integertarget
, return indices of the two numbers such that they add up to
target
.
 return indices of the two numbers such that they add up to

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
Top comments (0)