[LeetCode] Two Sum

https://leetcode.com/problems/two-sum/submissions/

 

숫자를 가진 배열 nums와 숫자값인 target이 있다.

이 때, 배열 nums 안에서 두 개의 숫자를 더해서 target이 되도록 구현하는 문제.

 

/*
@param {number[]} nums
@param {number} target
@return {number[]}
*/

var twoSum = function(nums, target){
    let x = nums.length;
    for(let i=0; i<x-1; i++){
        //console.log(i,"여기 들어옴")
        for(let j=i+1; j<x; j++){
            //console.log(i,j,nums[i],nums[j]);
            if(nums[i]+nums[j]==target){
                return[i,j]
            }
        }
    }
};

 

* i < x 로 했을 때와 i < x-1로 했을 때의 차이?

test input -> nums = [2,7,11,15] , target = 9

배열의 길이 nums.length를 x라고 해 주었다.

(1) i < x // 즉, i < 4 일때까지 돌도록 지정했으므로 i가 0부터 3까지 최대 4바퀴 돌 수 있다.

(2) i < x-1 // 즉, i< 3 일때까지 돌도록 지정했으므로 i가 0부터 2까지 최대 3바퀴 돌 수 있다.

그리고 j = i+1이므로 i와 작거나 같을 수 없다. 

i<x일 때

 

(1)에서 i = 3이면 j = 4이기 때문에 안쪽의 루프는 돌지 않는다.

이 때 안쪽 루프를 돌기 전에 i가 4보다 작은지 검사를 하게 된다.

 

i<x-1일 때

(2)에서는 i = 3이면 j = 4지만, 바깥쪽 루프의 범위(i < x-1 ⇢ 3 < 3) 에 걸리므로

바깥쪽 루프부터 시작하지 않게 된다.

∴ (2)가 (1)보다 효율적이다.

 

* var은 전역에서 쓸 수 있어 let으로 해 주는 게 낫다.