.png&blockId=5f7573ad-6867-4d59-999e-722aced04aeb)
Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
You can return the answer in any order.
Example 1:
Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].
Plain Text
복사
Example 2:
Input: nums = [3,2,4], target = 6
Output: [1,2]
Plain Text
복사
Example 3:
Input: nums = [3,3], target = 6
Output: [0,1]
Plain Text
복사
Constraints:
•
2 <= nums.length <= 10^4
•
-10^9 <= nums[i] <= 10^9
•
-10^9 <= target <= 10^9
•
Only one valid answer exists.
Follow-up:
Can you come up with an algorithm that is less thanO(n^2) time complexity?
My solution
정수 배열 nums와 정수 target이 주어진다. 더해서 target이 되는 두 숫자의 인덱스를 반환하라.
각 입력에는 정확히 하나의 답안만 있고, 같은 요소를 두번 사용할 수 없다.
답은 어떤 순서로도 반환될 수 있습니다.
it('TC1', () => {
expect(twoSum([2, 7, 11, 15], 9)).toStrictEqual([0, 1]);
});
JavaScript
복사
설명 : nums[0] + nums[1] == 9이니 [0, 1]을 반환한다.
hash map을 사용한다.
target이 9로 주어졌다면, 배열을 처음부터 방문하면서 요소를 매번 target에서 뺀 값을 저장한다.
이렇게 하면 target을 만들기 위해 필요한 숫자를 키로 하고, 그 숫자를 필요로 한 숫자가 있는 인덱스가 값으로 hash map에 저장되게 된다.
따라서 그다음 요소부터는 그 숫자가 이미 hash map에 존재하는지 확인해서 존재한다면 그 값(인덱스)를 꺼내서 배열에 담아 리턴하면 된다.
const hash = {};
for (let i = 0 ~ arr.length)
// hash에 존재하는지 확인, 해당 키가 존재하는지는 undefined인지를 확인해야 한다는 것을 주의한다.
if(hash[nums[i]] !== undefined)
return [hash[nums[i]], i]
hash[target - nums[i]] = i;
JavaScript
복사
Code
/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
const twoSum = function (nums, target) {
const hash = {};
for (let i = 0; i < nums.length; i++) {
if (hash[nums[i]] !== undefined) {
return [hash[nums[i]], i];
}
hash[target - nums[i]] = i;
}
};
describe('twoSum', () => {
it('TC1', () => {
expect(twoSum([2, 7, 11, 15], 9)).toStrictEqual([0, 1]);
});
it('TC2', () => {
expect(twoSum([3, 2, 4], 6)).toStrictEqual([1, 2]);
});
it('TC3', () => {
expect(twoSum([3, 3], 6)).toStrictEqual([0, 1]);
});
});
JavaScript
복사
