“This is my 32nd participation in the Inaugural Challenge 2022. For more details: Inaugural Challenge 2022”

1. Sum of two numbers

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:

Input: nums = [2,7,11,15], target = 9 output: [0,1]

Example 2:

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

Example 3:

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

 

Tip:

2 <= nums.length <= 104-109 <= nums[I] <= 109-109 <= target <= 109 there will only be one valid answer progression: Can you think of an algorithm whose time complexity is less than O(n2)?

Analysis of the

The sum of two numbers is a more classic problem. A. target b. target C. target D. target The thing to notice here is that the same element in the array can’t be repeated in the answer, and the same element here is not a number, it’s a subscript. For example nums = [5,5,2] target=10 obviously we should return [0,1].

So when we get to the problem and we talk about the solution, when we think about finding two numbers the first thing we should think about is that we can find the sum of two numbers by going through two loops.

After the basic solution we talk about the advanced solution, we can use the Map object to record the current index of the array numS elements and it needs the relationship between the array. Instead of iterating through the two sides of the NUMS array, we can just take the second number from the Map object. And of course in both the basic and the advanced solutions we have to be careful that the subscripts are not the same.

After analyzing the topic, let’s go straight to reality!!

Step by step brute force cracking

If nums[I]+nums[j] = target = = j. Return [I,j] if true, otherwise continue the next loop.

for(let i = 0; i<nums.length; i++){
        for(let j = 0; j<nums.length; j++){
            if(nums[i]+nums[j] === target && i ! == j){return [i,j]
            }
        }
    }
Copy the code

Code to achieve 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 = 0; j<nums.length; j++){
            if(nums[i]+nums[j] === target && i ! == j){return [i,j]
            }
        }
    }
    return[]}.Copy the code

A step-by-step implementation uses Map objects

Defines a map object that holds the relationship between the current subscript and the desired value

let map = new Map(a)Copy the code

Check if the value exists if it has been added to target, return the current index and the index stored in the map object. Otherwise, we store the desired number of targets and the current index in the map object.

for(let i = 0; i<nums.length; i++){
        let num = nums[i]
        if(map.has(num)){
            return [map.get(num),i]
        }else{
            map.set(target-num,i)
        }
    }
Copy the code

The code implementation uses a Map object

/ * * *@param {number[]} nums
 * @param {number} target
 * @return {number[]}* /
var twoSum = function(nums, target) {
    let map = new Map(a)for(let i = 0; i<nums.length; i++){
        let num = nums[i]
        if(map.has(num)){
            return [map.get(num),i]
        }else{
            map.set(target-num,i)
        }
    }
    return[]}.Copy the code