preface

To participate in an activity of swiping questions in the Nuggets community, simply speaking, it is to publish 10 articles about algorithm and swiping questions in the Nuggets community before March 13 (inclusive). After completion, there will be some gifts, such as 1 discount card of the nuggets booklet and so on. This post shares the LeetCode solution for problem 1 and the Python 3 and JavaScript solution code.

Topic describes

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

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

You can return the answers in any order.

Difficulty: ** Easy

Example:

Enter: nums = [2.7.11.15], target = 9Output:0.1] Cause: because nums[0] + nums[1] = =9To return to the [0.1].Copy the code

Tip:

  • There can only be one valid answer
  • 2 <= nums.length <= 103
  • -109 <= nums[i] <= 109
  • -109 <= target <= 109

Their thinking

Just saw this problem, a few words popped out of my mind: two layers of circulation. The first loop iterates through the array in turn. The second loop iterates through the array starting with the index value of the first loop and determines whether the sum of the current values of the first and second loops is target. If so, it returns the index value of the two loops. The Internet also enumerates violence in this way. Since it is a brute force solution, there must be optimization methods. Is it possible to sacrifice some spatial performance in exchange for faster execution? Let’s move on.

Think about the way of problem solving, you will find that this approach will record the current element in an array, and then in the array is not found in traversal of the element and a matching result value, has been through the element to be discarded, drain the cycle time, we can put the traversal, making use of elements from these to traverse the searching and matching the value of the current value in the element. This requires some way to pair the iterated elements with their corresponding indexes. What do you think of at this point, objects or dictionaries? By the way, dictionaries can be used to store traversal values. We use the iterated element as the dictionary key and its corresponding index value as the value. If target-currentValue is a key in the dictionary, you can use target-currentValue as a key in the dictionary.

Next, I’ll show you how Python3 and JavaScript solve this problem, with Python3 introducing the 2 solution and JavaScript introducing only the 2 solution.

AC code

Python3

Violence iteration method

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

        for i in range(nums_length):
            for j in range(i + 1, nums_length):
                if nums[i] + nums[j] == target:
                    return [i, j]
        
        return [0.1]
Copy the code

Dictionary lookup

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

JavaScript

var twoSum = function(nums, target) {
    const hashTable = new Map(a)for(let i = 0; i < nums.length; i++) {
        if (hashTable.has(target - nums[i])) {
            return [hashTable.get(target - nums[i]), i]
        }

        hashTable.set(nums[i], i)
    }

    return[]}.Copy the code

conclusion

The time complexity of violent iteration is O(n^2) because there are two layers of traversal. In the implementation process, only three variables are defined, and its spatial complexity is O(1).

Dictionary lookup, which only requires traversal, is O(n) in time; In the implementation process, we need to create a dictionary to store the element values to be traversed, which has O(n) space complexity. Compared with the violent iteration method, this method sacrifices some space in exchange for faster execution speed.

Side note: Maps in JavaScript

Map is a collection tool added to ES6. A Map is an ordered list that stores many key-value pairs, where keys and values support all data types. Keys in maps use object.is () for equivalence purposes, as opposed to property names in objects, which are always forced to be strings when compared. For example, a numeric 5 and a string “5” are judged to be two different types in a Map, corresponding to two keys, whereas in an object, when the two are compared, 5 is forced to be “5” and treated as the same property name.

Instantiation of a Map: Use the new Map() method to create instances. You can also pass an array to the Map constructor during initialization, but the array must be two-dimensional, for example:

let mapInstance = new Map([["name"."jiaoxn"], ["age".27]])
Copy the code

Name and age are the keys in the Map, and jiaoxn and 27 are the corresponding values.

Map method:

  • has(key)To determineMapWhether there is akey
  • delete(key), fromMapDeleted from an instancekeyAnd its corresponding value
  • clear()To removeMapAll key-value pairs of the instance
  • set(key, value)toMapAdd key-value pairs to the instance
  • get(key)To obtainMapOne of the instanceskeyThe value of the
  • foreach()To traverse theMapThe value of the element in the instance, and the argument is a callback function that takes three arguments: the value, the key name, and the instance itself.
let mapInstance = new Map()

mapInstance.set('name'.'jiaoxn')
mapInstance.set('age'.27)

mapInstance.foreach((value, key, ownerMap) = > {
    console.log(value, key)
    console.log(ownermap)
    console.log(ownermap === mapInstance)
})
Copy the code