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:
- The number in the array cannot be reused
- 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
- While traversing, some information is recorded to save a layer of circulation, [space for time]
- 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 } } }