two sum #1 알고리즘 문제

Two Sum

정수로 이루어진 배열 nums 와 정수인 target 이 있습니다.

배열 내, 두개의 요소를 합하여 target 이 되는 인덱스 두개를 배열로 return 하시면 됩니다. 

Ex)
Input: nums = [-1,2,7,11,15,23], target = 9
Output: [1,2]

Ex2)
Input: nums = [3,2,4], target = 6
Output: [1,2]
Example 3:

Ex3)
Input: nums = [3,3,4], target = 6
Output: [0,1]

 

답

Brute Force

var twoSum = function(nums, target) {
    for (let i = 0; i < nums.length; i++) {
        for (let j = i + 1; j < nums.length; j++) {
            if (nums[i] + nums[j] == target) {
                return [i, j]
            }
        }
    }
};

시간 복잡도: O(n^2)

공간 복잡도: O(1)

 

One-pass HashMap

var twoSum = function(nums, target) {
	let obj = {};
	for(let i = 0; i < nums.length; i++) {
		const n = nums[i];
		if(obj[target - n] !== undefined) {
			return [obj[target - n], i];
		}
		obj[n] = i;
	}
	return [];
}

시간 복잡도: O(n)

공간 복잡도: O(n)

 

Two-pass HashMap

var twoSum = function(nums, target) {
    const numIdx = {};

    for (let i = 0; i < nums.length; i++) {
        numIdx[nums[i]] = i;
    }
    
    for (let i = 0; i < nums.length; i++) {
        const c = target - nums[i];
        if (c in numIdx && numIdx[c] !== i) {
            return [i, numIdx[c]];
        }
    }
    return [];
};

시간 복잡도: O(2n)

공간 복잡도: O(n)