Leetcode 1. sum of two numbers

1. Sum of two numbers

Power button ：1. Sum of two numbers

Method 1 ： Enumeration （ Brute force ）

Time complexity  

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

utilize len() Function to get the length of the array and assign it to n

Then two layers of circulation .

Because the title requires that the same element cannot appear twice , therefore i and j Must be different . So the inner loop j The range is from i+1 Start .

When the loop finds the array nums[i]+nums[j] be equal to target when , Returns the subscript i, and j.

Because there may not be a suitable i and j, And the function must have a return value , So finally add return[]

LeetCode Medium

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:

stay pycharm An error will be displayed in ,NameError: name 'List' is not defined

Import typing Bag can

from typing import List

  because python Too casual , It's easy to forget to pass parameter types . So it introduces typing modular , Variable types can be specified .

• typing Role of module ：

1. Type checking , Prevent non conformance of parameter and return value types at runtime .
2. As a development document , It is convenient for the user to pass in and return parameter types when calling .
3. The addition of this module will not affect the operation of the program , Don't report a formal mistake , Only reminders .

pycharm Running test results

Method 2 ：

Hash table method

Time complexity

hash function

function ： input data , Generating integers

The main features ：1. Different parameters -> Different integers

                2. The same parameters -> Same integer

Some functions used

Python enumerate() function

enumerate() Function is used to traverse a data object ( As listing 、 Tuples or strings ) Combined into an index sequence , List both data and data index , Generally used in for Cycle of .

 grammar 
enumerate(sequence, [start=0])

 

Python dict() function

dict()  Function to create a dictionary .

Python dict() function | Novice tutorial

Using hash table algorithm

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

pycharm test result