1. The subject

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:

Nums = [2,7,11,15], target = 9 output: [0,1]Copy the code

• Example 2:

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

• Example 3:

Input: nums = [3,3], target = 6Copy the code

Tip:

• 2 <= nums.length <= 10⁴
• -10⁹ <= nums[i] <= 10⁹
• -10⁹ <= target <= 10⁹
• There can only be one valid answer

** Can you think of an algorithm whose time complexity is less than O(n2)?

2. Violence is a soha

So let’s go through two loops

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

3. Optimization of violence method

Check if the same number has been checked each time in the outer loop

var twoSum = function(nums, target) {
  const record = []
  for(let i = 0; i < nums.length; i++) {
    if(record[nums[i]]) {
      continue
    }
    for(let l = i + 1; l < nums.length; l++) {
      if(nums[i] + nums[l] === target) {
        return [i, l]
      }
    }
    record[nums[i]] = true}};Copy the code

Because the time is still order n²), so you can see that the optimization is not much

4. Hash table solution

In the space for time violence solution, the purpose of the second loop is to find the elements that match I. Since the array is not ordered, we have to go through them one by one. With a hash table, we can reduce this process to ** O(1) complexity **.

const twoSum = function(nums, target) {
  const length = nums.length
  const map = new Map(a)for(let i = 0; i < length; i++) {
    const needNum = target - nums[i]
    if(map.has(needNum)) {
      return [map.get(needNum), i]
    }
    map.set(nums[i], i)
  }
}
Copy the code