“This is the first day of my participation in the Gwen Challenge in November. Check out the details: The last Gwen Challenge in 2021”

The title

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)?

Their thinking

Arr [I] = arr[j] = arr[j] = arr[I] = arr[j] = target

【 Method 1: For loop brute force cracking 】

/ * * *@param {number[]} nums
 * @param {number} target
 * @return {number[]}* /
var twoSum = function(nums, target) {
    for(let i = 0; i < nums.length; i++) {
        for(let j = i+1; j < nums.length; j++) {
            if (nums[i] + nums[j] === target) {
                return[i, j]; }}}return [];
};
Copy the code

But those of you who are familiar with time complexity know that when we nested for loops, time complexity is n to the power of nesting. That is, the time responsibility of the current method is O(N2).

Although this method wastes time complexity, it does not create any extra space to store data, so the space complexity is O(1);

Conclusion:

  • Time complexity: O(N2)
  • Space complexity: O(1)

There should be a better way to solve the problem of time complexity

Or can we trade space for time?

In ES6, we learned that MAP sets can store key-value pairs (hash structures).

You can obtain a MAP instance by using new MAP()

Map instance has properties and methods:

  • Size property: Can get the total number of map instance members (length)
  • The set method:set(key, value)Set the key corresponding to the key. If the key already has a value, it will be updated
  • The get method:get(key)Read the value of the corresponding key, if not return undefined
  • From the method:has(key)Check whether the key exists in the MAP structure and return a Boolean value
  • The delete method:delete(key)Delete a key, return true if it was/successfully deleted, false otherwise
  • The clear method:clear()Clear all MAP members

Therefore, we can create a new MAP space to store the required values, and then add or obtain a value according to the set and GET methods of the MAP to solve the problem.

【 Method 2: MAP set/Hash structure 】

/ * * *@param {number[]} nums
 * @param {number} target
 * @return {number[]}* /
var twoSum = function(nums, target) {\\ Create a map instancelet map = new Map(a); \\ Traverse the number group to read and save the judgmentfor(let i = 0; i < nums.length; I++) {\\ get the value we need from the target value - current valueletx = target - nums[i]; \\ Determine if there are any values in the map that we needif(map.has(x)) {\\ Returns the key of the current value if there is a desired value in the collectionreturn[map.get(x), i]; } \\ If there is no current value in the set, store the current value in the key of the map. }return [];
};
Copy the code