This is the second day of my participation in the August Text Challenge.More challenges in August

The sum of two numbers LeetCode

Given an integer array nums and an integer target value target, find the two integers in the array and the target value target and return their array subscripts.

You can assume that there is only one answer for each type of input. However, the same element in the array cannot be repeated in the answer.

You can return the answers in any order.

Example 1:

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

Output: [0, 1]

Because nums[0] + nums[1] == 9, return [0, 1]

Example 2:

Enter: nums = [3,2,4], target = 6

Output: [1, 2]

Example 3:

Enter: nums = [3,3], target = 6

Output: [0, 1]

Tip:

2 <= nums.length <= 104

-109 <= nums[i] <= 109

-109 <= target <= 109

There can only be one valid answer

Advanced: Can you think of an algorithm whose time complexity is less than O(n2)?

Subject analysis

1. The boundary value of the prompt is no longer considered by the program

2. Target and array are integers

3. The array length must be greater than or equal to 2, which is the starting point for thinking

4. Instead of returning the element as target, the index of the element can be returned in any order

Python algorithms tend to prioritize type characteristics before built-in functions and operators

coded

>>> It’s still Python

class Solution:
    def twoSum(self, nums: List[int], target: int) - >List[int] :
        for i in range(len(nums)):
            subx=target-nums[i]
            if subx in nums:
                index=nums.index(subx)
                ifi! =index:return [i,index]
Copy the code

The submitted code execution results are as follows

The code analysis

[I]= (select * from list) [I]= (select * from list) [I]= (select * from list) [I]= (select * from list) [I]= (select * from list) [I]= (select * from list) [I]= (select * from list)

L From the result, the execution time is not ideal, obviously this algorithm is not good

L And this way of thinking, the index method of the list type is defective

Violence algorithm

Both are brute force algorithms, each element does a match lookup, but the last I! =index is a little hard to understand

class Solution:
    def twoSum(self, nums: List[int], target: int) - >List[int] :
        count=len(nums)
        for i in range(count):
            for j in range(i+1,count):
                if nums[i]+nums[j]==target:
                    return [i,j]
        return []
Copy the code

This brute force algorithm, the result is not optimized

Parsing: By iterating through the list, the second layer of for matches the second element. The first layer sums each element with the next element to get the index. So it takes more time than the first solution.

The new knowledge

Hash: For each x, we first check whether target-x exists in the hash table, and then insert x into the hash table to ensure that x does not match us

class Solution:
    def twoSum(self, nums: List[int], target: int) - >List[int] :
        hashtable = dict(a)for i, num in enumerate(nums):
            if target - num in hashtable:
                return [hashtable[target - num], i]
            hashtable[nums[i]] = i
        return []
Copy the code

Official record

In terms of execution time, it is better than the first and second solutions.