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.