Title:

Given an integer array nums and a target value target, please find the two integers in the array whose target value is sum and return their array subscripts.

You can assume that each input corresponds to only one answer. However, the same element in an array cannot be used twice.

Example:

Given nums = [2, 7, 11, 15], target = 9, because nums[0] + nums[1] = 2 + 7 = 9, return [0, 1]

Initial solution:

1. The number in the array cannot be reused
2. Returns an array

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {
    let result = []
    nums.map((first,i) => {
        let secondIndex = i + 1
        let second = nums[secondIndex]
        let sum = first + second
        if(sum === target) {
            result.push(i,secondIndex)
        }
    })
    return result
};

Conclusion: the example test is passed, but the case of [3,2,3] and target = 6 is not considered

After consideration, it is revised as follows:

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {
    let result = []
    nums.map((first,i) => {
        let secondIndex = i + 1
        nums.forEach((second,j) => {
            let sum = first + second
            if(j >= secondIndex && sum === target) {
                result.push(i,j)
            }

        });
    })
    return result
};

Expert solution:

Master:@ tboys

Thinking of solving problems

Hashtable

1. While traversing, some information is recorded to save a layer of circulation, [space for time]
2. Need to record the traversed value and its corresponding subscript, with the help of look-up table

Realization idea

When traversing to the number a, subtract a from target to get B. If b exists in the hash table, we can return the result directly. If B does not exist, then we need to store aa into the hash table, so that the subsequent traversal numbers can be used.

Big brother has Animation illustration It's easy to read@ demigodliu

Knowledge points:

Hash table is also known as hash table. Hash table is a special data structure, which is obviously different from array, stack, linked list and so on. It can quickly locate the records to be searched, instead of comparing with the keywords of the records in the table.

Hash table is a data storage structure based on key value pairs. The key value can not be repeated, and the value can be repeated. When the repeated key value is added later, the value corresponding to the previous key value will be covered. Objects in JavaScript have natural hash characteristics.

Map Object to save key value pairs and remember the original insertion order of keys. Any value (object or original value) can be used as a key or a value.

Compared with Object, the performance of Map is better in the scene of frequent addition and deletion of key value pairs

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {
    let len = nums.length;
    // Create MAP
    const MAP = new Map();
    /**
    *Map.prototype.set(key, value)
		*Sets the value of the key in the Map object. Returns the Map object.
    */ 
    // Since the first element must have no element before it to match, it is stored in the hash table first
    MAP.set(nums[0], 0);
    for (let i = 1; i < len; i++) {
        // Draw share
        let other = target - nums[i];
        // Judge whether the condition is met and return the corresponding subscript
        if (MAP.get(other) !== undefined) return [MAP.get(other), i];
        // The inconsistent data are stored in hash table
        MAP.set(nums[i], i)
    }
};

Objects in JavaScript have a natural hash property

Source:@ xiao_ben_zhu

const twoSum = (nums, target) => {
  const prevNums = {};                    // Store the number that appears, and the corresponding index               

  for (let i = 0; i < nums.length; i++) {       // Traversal element   
    const curNum = nums[i];                     // Current element   
    const targetNum = target - curNum;          // Target elements that meet the requirements   
    const targetNumIndex = prevNums[targetNum]; // Get the index of the target element in prevNums
    if (targetNumIndex !== undefined) {         // If it exists, directly return [index of target element, current index]
      return [targetNumIndex, i];
    } else {                                    // If it does not exist, the target element has not appeared before
      prevNums[curNum] = i;                     // Save the current element and corresponding index
    }
  }
}