투썸
정수 배열 nums와 정수 대상이 주어지면 두 숫자의 인덱스를 반환하여 대상에 합산되도록 합니다.
예 1:
Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Output: Because nums[0] + nums[1] == 9, we return [0, 1].
예 2:
Input: nums = [3,2,4], target = 6
Output: [1,2]
예 3:
Input: nums = [3,3], target = 6
Output: [0,1]
분석
따라서 배열에 대해 2개의 숫자가 있어야 그 합이 목표 합계와 같게 됩니다. 심플한 느낌 :-) ...
하지만 정렬되지 않음
먼저 생각나는 것은 각 요소를 취하고 나머지 요소에서 요소의 대상 보완을 찾는 것입니다.
So this will take O(n^2) and space complicity of O(1)
우리는 더 나은 시간 공모를 가질 수 있습니까?
당신!! 우리는 가지고 있습니다!
target 보수(target - currentValue)를 키로 유지하고 인덱스를 값으로 유지하는 해시를 유지할 수 있으며 해시 맵에서 요소를 찾으면 해시 맵에서 현재 인덱스와 인덱스를 반환합니다.
코딩하자!
var twoSum = function (nums, target) {
result = [];
const index_map = new Map();
// Loop for each element in the array
for (let i = 0; i < nums.length; i++) {
let difference = target - nums[i];
if (index_map.has(difference)) {
result.push(i);
result.push(index_map.get(difference));
break;
} else {
index_map.set(nums[i], i);
}
}
return result;
};
So, Here the time complicity is O(n) and space complicity of O(n).
결론
최고의 시간 공모 알고리즘은 해시 맵을 사용하는 것이지만 O(n) 공간 공모가 필요할 수 있습니다.
시간과 공간 중 어느 것이 요구 사항인지 항상 생각하고 알고리즘을 생각해 냅니다.
감사합니다 연락하고 계속 배우십시오!
Reference
이 문제에 관하여(투썸), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://dev.to/akhilmdev/two-sum-eaf텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)