1. sum of two numbers Python leetcode

Hello everyone , I meet you again , I'm your friend, Quan Jun .

At the beginning, I just touched the algorithm , I don't know much about it , I plan to tidy up every time I brush a question

subject ：

Give a sequence of integers , Find the two numbers where the sum is a specific value .

You can assume that each input has only one answer , The same element cannot be reused .

Example :

 Given nums = [2, 7, 11, 15], target = 9
because nums[0] + nums[1] = 2 + 7 = 9
So back [0, 1]

Solution 1 ：. When I first saw it , The first thought is to use a nested loop to put nums List traversal twice , Although the test passed, it took too long , Then we consider other methods with low time complexity

The code is as follows ：

class Solution:
def twoSum(self,nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
# use len() Method acquisition nums The length of the list
n = len(nums)
#x The values from 0 Until n（ barring n）
for x in range(n):
#y The values from x+1 Until n（ barring n）
# use x+1 Is to reduce unnecessary circulation ,y The value of must be greater than x Big
for y in range(x+1,n):
# If target-nums[x] A value of exists in nums in
if nums[y] == target - nums[x]:
# return x and y
return x,y
break
else:
continue

Solution 2 ： Use one for loop , Query directly inside target-nums[x] Does it exist in nums In the list , The speed is much faster than solution one , But it's not enough

The code is as follows ：

class Solution:
def twoSum(self,nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
# use len() Method acquisition nums List length
n = len(nums)
#x from 0 To n Value （ barring n）
for x in range(n):
a = target - nums[x]
# use in Keyword query nums Is there... In the list a
if a in nums:
# use index Function acquisition a The value of the nums Index in the list
y = nums.index(a)
# If x=y, Then skip , Otherwise return to x,y
if x == y:
continue
else:
return x,y
break
else :
continue

Solution 3 ： This solution is only known after I read the top several answers , First create an empty dictionary , Then put them in turn target-nums[x] The value of is stored in the dictionary , Depositing one is like nums[x+1] To compare , In the dictionary key by target-nums[x],value by x, That is to say nums[x] stay nums Index position in the list . Be a dictionary d There is nums[x+1] when , That is to say target – nums[y] = nums[x+1] , y It must be less than x+1 Of ( because y yes x+1 Numbers that have been cycled before )

So it is return y,x+1

class Solution:
def twoSum(self,nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
# use len() Method acquisition nums List length
n = len(nums)
# Create an empty dictionary
d = {}
for x in range(n):
a = target - nums[x]
# Dictionaries d in nums[x] when
if nums[x] in d:
return d[nums[x]],x
# Otherwise, add a key to the dictionary / It's worth it
else:
d[a] = x
# Add keys to the dictionary / It's worth it , Edge and nums[x] Contrast 

Publisher ： Full stack programmer stack length , Reprint please indicate the source ：https://javaforall.cn/133633.html Link to the original text ：https://javaforall.cn