Title description:

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

Enter: nums = [2, 7, 11, 15], target = 9

Output: [0, 1]

Solution idea 1: two layers of traversal

function twoSums(nums, target) {
    for(let i = 0; i< nums.length; i++) {
        for(let j=i+1; j< nums.length; j++){
            if(nums[i] + nums[j]) {
                return [i, j]
             }
        }
    }

}
Copy the code

If nums[I] + nums[j] === target, return [I,j], O(n^2)

Solution idea 2: a layer traversal

The sum problem can generally be transformed into the difference problem

IndexOf finds another indexOf target-num [I]

function twoSums2(nums, target) {
    for(let i = 0; i< nums.length; i++) {
        let index = nums.indexOf(target - nums[i])
        if(index ! = = -1&& index ! == i) {return [i, index]
         }
    }
}

Copy the code

With the help of other data structures

In the algorithm, space for time often exists, good at using Map, Set and other data structures, and the function of Map can often be realized by {}

function twoSums3(nums, target) {
    const res = {}
    for (let i = 0; i< nums.length; i++) {
        if(res[target - nums[i]] ! = =undefined) {
            return [i, res[target - nums[i]]]
        } else {
             res[nums[i]] = i // Record the current index}}}Copy the code