크러싱 취업 면접(DSA) - 두 숫자 합계

질문

난이도: 쉬움

개별 정수의 비어 있지 않은 배열과 목표 합계를 나타내는 정수를 받는 함수를 작성하세요. 입력 배열에 있는 두 숫자의 합계가 목표 합계에 도달하면 함수는 순서에 상관없이 배열에 반환해야 합니다. 두 숫자의 합계가 목표 합계에 도달하지 않으면 함수는 빈 배열을 반환해야 합니다.

목표 합계는 배열에 있는 두 개의 서로 다른 정수를 합산하여 얻어야 합니다. 목표 합계를 얻기 위해 단일 정수를 자체에 추가할 수 없습니다.

목표 합계까지 합산되는 숫자 쌍이 많아야 한다고 가정할 수 있습니다.

샘플 입력

array = [3, 5, -4, 8, 11, 1, -1, 6]
targetSum = 10

샘플 출력

[-1, 11] // the numbers could be in reverse order

최적의 공간 및 시간 복잡성:

O(n) 시간 | O(n) 공간 - 여기서 n은 입력 배열의 길이입니다.

생각

지루한 수학 교수님의 수업에 주의를 기울였다면 이 솔루션을 아주 쉽게 생각해낼 수 있었을 것입니다.

그래서 말하자

// 10 is the target sum
10 = x + y
// so
y = 10 - x

P.S: Hashmap is just a object in javascript or dictionary in python.

이제 우리가 할 일은 해시맵을 만들고 우리에게 주어진 배열을 반복하는 것입니다. 그런 다음 우리는:

해시에 y가 있는지 확인합니다. 즉, 10 - x

값이 있으면 x와 y가 모두 있으므로 배열을 반환합니다

.

그렇지 않은 경우 해당 숫자를 해시맵에 추가합니다

.

해결책

function twoNumberSum(array, targetSum) {
    const nums = {} // this is the hashmap

  for (let num of array){
    if (nums[targetSum - num] ) return [targetSum-num, num]
    nums[num] = true
  }

  return []
}

의심의 여지가 있습니까? 더 나은 솔루션이 있습니까? 아래에 의견을 남기고 토론을 시작합시다.

코딩에 대한 더 멋진 콘텐츠를 보려면 인스타그램에서 나를 팔로우하세요.