[leetcode] Two Sum

1 . Two Sum

정수 배열 nums 과 정수가 주어지면 두 숫자의 합이 가 되도록 인덱스 target을 반환합니다.

각 입력에 정확히 하나의 솔루션이 있다고 가정할 수 있으며 동일한 요소를 두 번 사용할 수 없습니다 .

어떤 순서로든 답변을 반환할 수 있습니다.

 

예 1:

입력: nums = [2,7,11,15], target = 9

출력: [0,1]

설명: nums[0] + nums[1] == 9이므로 [0, 1]을 반환합니다.

 

예 2:

입력: 숫자 = [3,2,4], target = 6

출력: [1,2]

 

문제정리

*정수란, 음의 정수 양의 정수 1,2,3,-4 을 말한다.

1. nums 배열과 target에 들어있는 숫자들은 정수이다.

2. nums 배열안에 있는 정수들을 더한 값이 target의 정수가 되는 지점(index)을 출력한다.

3. 같은 요소는 두번 사용 할 수 없다.

 

생각한 풀이방법

 

1. for문을 사용해서 배열을 순회한다.

2. 배열의 첫번째 정수와, 두번째 정수를 비교해서 target 정수가 되면 그 정수의 index를 반환한다.

3. 조건에 성립되면 배열안에 해당하는 i, j를 넣어준다.

 

출력코드📍

function twoSum(nums, target) {
   for (let i = 0; i < nums.length; i++) {
   // i는 0부터 시작해서 nums의 길이보다 작을 때까지 1씩 증가한다.
     for (let j = i + 1; j < nums.length; j++) {
    //배열의 첫번째 숫자와 두번째 숫자를 더해서 target과 같은지 확인해야 하므로 j는 i+1부터 시작한다.
     //j+1은 i+2가 되므로 두번째 숫자와 세번째 숫자를 더하는 것이다.
       if (nums[i] + nums[j] === target) {
      // 두 숫자를 더해서 target과 같으면
     return [i, j]; // i와 j를 배열로 만들어서 리턴한다.
      }
    }
  }
}
let a = [3, 2, 4];
let b = 6;
console.log(twoSum(a, b));

 

1. 이중for문을 사용한 이유.

이중 for문을 사용하여 모든 요소 쌍을 비교하여 조건을 만족하는 요소의 인덱스를 찾을 수 있습니다.

하지만 이중 for문은 실행 시간이 길어질 수 있으므로, nums 배열이 매우 큰 경우 성능 문제가 발생할 수 있습니다.

효율적인 알고리즘은 해시 테이블(Hash Table)을 이용한 알고리즘을 사용하는 방법도 있습니다.