1. Title Description

Given an integer array nums and an integer 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, the same element in an array cannot be used twice.

You can return the answers in any order.

Example 1:

Input: 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^3
  • 10^9 <= nums[i] <= 10^9
  • 10^9 <= target <= 10^9
  • There can only be one valid answer

Second, train of thought analysis

The basic idea of this problem is as follows:

Two layers of loop through the same array; The value of the first loop is value1, and the value of the second loop is value2. If value1+value2 = the target value, then the array subscripts for value1 and value2 are the answers we want.Copy the code

!!!!!!!!! Note that two-level loops often mean O(n^2) complexity, which can easily cause the algorithm to time out and must be optimized.

Try swapping space for time and optimizing it into a layer of loops:

We can add a Map to record the numbers that have been iterated and their corresponding index values while iterating through the array. Each time a new number is iterated, go back to the Map to see if the difference between targetNum and that number has already occurred in the previous number. If so, the answer is already there, and we don't have to go any further.Copy the code

AC code

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

Four,

  • When you find yourself with a two-layer loop in your code, ask yourself if you can optimize it into a one-layer loop by swapping space for time.
  • Almost any sum problem can be transformed into a difference problem. So this is a classic example of a problem that makes things a lot easier by turning the sum problem into a difference problem.

This article is participating in the “Nuggets 2021 Spring Recruitment Campaign”, click to see the details of the campaign