📄

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.

You can assume that there is only one answer for each type of input. However, you cannot reuse the same elements in this array.

Topic analysis 🧐

One, violent search

  • Double loop, try every possible sum
  • findnums[i] + nums[j] === targetWhen to return to[i, j]
/** * @param {number[]} nums * @param {number} target * @return {number[]} */
var twoSum = function(nums, target) {
    const len = nums.length
    for (let i = 0; i < len - 1; i++) {
        for (let j = i + 1; j < len; j++) {
            if (nums[i] + nums[j] === target) {
                return [i, j]
            }
        }
    }
}
Copy the code
  • Time complexity:O(n^2)
  • Space complexity:O(1)

Idea 2, space for time — clever use of hash table

  • willtarget - nums[i] 和 iThe value ofHash table,target - nums[i]The correspondingi
  • traversenumsArray, find one that exists inHash tableIn thenums[i]Find two numbers that add up to equaltarget
/** * @param {number[]} nums * @param {number} target * @return {number[]} */
var twoSum = function(nums, target) {
    const map = new Map(a)for (let i = 0; i < nums.length; i++) {
        map.set(target - nums[i], i)
    }
    for (let i = 0; i < nums.length; i++) {
        const ans = map.get(nums[i])
        if(ans && ans ! == i) {return [ i, map.get(nums[i]) ]
        }
    }
}
Copy the code

In fact, you can also optimize the loop into one, with the following code 🌰 :

/** * @param {number[]} nums * @param {number} target * @return {number[]} */
var twoSum = function(nums, target) {
    const map = new Map(a)for (let i = 0; i < nums.length; i++) {
        const ans = target - nums[i]
        if (map.has(ans)) {
            return [ i, map.get(ans) ]
        }
        map.set(nums[i], i)
    }
}
Copy the code
  • Time complexity:O(n)
  • Space complexity:O(n)

Write in the last

I have been brushing questions on LeetCode and joined the organization before. If you are interested in learning together, you can leave a message below or follow my wechat public account “Tony’s Front-end Cram School” and leave a message in the background. You can join the group to learn with the big guys.