preface
About the LeetCode array type problem related solutions, it can be seen that LeetCode array type problem before doing must see, classification solution summarized the problem, can be used to improve a single. If you think it is helpful, remember to give more likes and attention, thank you!
Topic describes
Given an integer array nums and an integer target, find the two integers in the array whose sum is target and return their array indices.
You can assume that there is only one answer for each input. However, the same element in the array must not appear repeatedly in the answer.
You can return the answers in any order.
Example: input: nums = [2,7,11,15], target = 9 output: [0,1] explanation: because nums[0] + nums[1] == 9, return [0,1]
Link: leetcode-cn.com/problems/tw…
Answer key
- In the brute force solution, we iterate through each element starting at 0, and after that element, we look for the element whose sum is equal to target. The time is n ^ 2, and I won’t go into that much here.
- If we use the hash method and store the array value as the key and the array index as the value in the map, when we iterate over one of the elements, we just need to determine whether (target – the current element) is a key of the map to determine whether there is an answer. This scheme is often called space for time, and the time complexity of this method is O(n).
/ * * *@param {number[]} nums
* @param {number} target
* @return {number[]}* /
var twoSum = function (nums, target) {
const map = new Map(a);for (let [i, n] of nums.entries()) {
if (map.has(target - n)) {
return [map.get(target - n), i];
}
map.set(n, i); // Store n while traversing, reducing the number of traversing and avoiding the same element repeated
}
return [];
};
Copy the code