preface

As the name suggests, the main purpose of this blog is to record the process of writing problems in Leetcode. The whole code is written in Python3. The website is Leetcode China. The advantages of this website are: 1) Pure Chinese, to solve the problem of difficult reading English; 2) Fast webpage opening. In addition to the python3 solution code for each problem, this column will try to use a variety of solutions, and also record some of my own insights and thoughts during the process of doing the problem. Facilitate later review consult.

The title

Given an array of integers and a target value, find two numbers that neutralize the target value in the array. You can assume that there is only one answer for each input and that the same elements cannot be reused.

Example:

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

Nums [0] + nums[1] = 2 + 7 = 9

Violent solution

First of all, let’s try the brute force solution.

class Solution:
    def twoSum(self, nums, target):
        """ :type nums: List[int] :type target: int :rtype: List[int] """
        renum = []
        n = len(nums)
        for i in range(n):
            for j in range(i+1,n):
                if nums[i]+nums[j] == target:
                    renum.append(i)
                    renum.append(j)
                    break   
        return(renum)
Copy the code

[Note] : For a function, the program automatically stops after executing return(), that is, in the function, return has the break function. So, a small optimization can be made to the code above: write return() directly at break. Something like this:

...if nums[i]+nums[j] == target:
	renum.append(i)
	renum.append(j)
	return(renum) # Break = return
Copy the code

However, due to the time complexity of such a violent solution, it is generally unable to pass Leetcode, and an error will be reported as follows:

Method two: establish hash table to solve.
class Solution:
    def twoSum(self, nums, target):
        """ :type nums: List[int] :type target: int :rtype: List[int] """
        dic = {}
        for i, num in enumerate(nums):
            if num in dic:
                return [dic[num], i]
            else:
                dic[target - num] = i
Copy the code

The dic key: target-num, value: the index of the dictionary values formed by the original List. If a numS value is detected that already exists in the new dictionary, the proof can form a target value that returns the index traversed at this point and the index recorded in the dict.

Method 3: Use Python slicing.
class Solution:
    def twoSum(self, nums, target):
        for i in range(len(nums)):
            if target-nums[i] in nums[i+1] :return [i,nums.index(target-nums[i],i+1)]
Copy the code
Solution:
1. Use of the enumerate() function

The enumerate() function forms a dictionary from a List in ascending order of indexes. Python enumerate Usage summary

2. A template for defining classes in Python