프로그래밍 「 자바스크립트 편」JS 코드 챌린지: 정렬된 배열에서 쌍 찾기

코딩 인터뷰에서는 배열에서 특정 목표 합계에 해당하는 숫자 쌍을 찾아야 하는 문제가 발생하는 것이 일반적입니다. 이 기사에서는 입력 배열이 정렬되는 "Two Sum II" 문제를 살펴보겠습니다. 이 문제를 해결하기 위한 알고리즘 접근 방식에 대해 논의하고 JavaScript로 코드 구현을 제공합니다.

님이 촬영 한 사진 게릴라버즈 on Unsplash

문제 설명:

정렬된 정수 배열과 목표 합계가 주어지면 배열에서 목표 합계에 합산되는 두 개의 숫자를 찾아야 합니다. 이 두 숫자의 인덱스를 배열로 반환해야 합니다.

알고리즘 접근법 :

이 문제를 효율적으로 해결하기 위해 2포인터 기술을 사용할 수 있습니다. 배열의 시작 부분(왼쪽 포인터)과 끝(오른쪽 포인터)에 하나씩 두 개의 포인터로 시작합니다. 이 포인터의 숫자 합계를 목표 합계와 비교합니다. 합계가 목표와 같으면 두 숫자의 인덱스를 반환합니다. 합계가 목표값보다 작으면 왼쪽 포인터를 증가시켜 더 큰 숫자를 고려합니다. 합계가 목표값보다 크면 더 작은 숫자를 고려하기 위해 오른쪽 포인터를 감소시킵니다. 우리는 한 쌍을 찾거나 모든 가능성을 소진할 때까지 이 과정을 반복합니다.

JavaScript의 코드 구현:

const twoSum = (numbers, target) => {
  let left = 0;
  let right = numbers.length - 1;
  while (left < right) {
    const sum = numbers[left] + numbers[right];
    if (sum === target) {
      return [left + 1, right + 1]; // Return indices (1-based)
    } else if (sum < target) {
      left++;
    } else {
      right--;
    }
  }
  return []; // No pair found
};
// Example usage
const numbers = [2, 7, 11, 15];
const target = 9;
const result = twoSum(numbers, target);
console.log(result); // Output: [1, 2]

설명:

1. 왼쪽 포인터는 배열의 시작 부분(인덱스 0)으로, 오른쪽 포인터는 배열의 끝(인덱스)으로 초기화합니다.numbers.length - 1
2. while 루프의 각 반복에서 왼쪽 및 오른쪽 포인터에 있는 숫자의 합을 계산합니다.
3. 합계가 목표값과 같으면 인덱스가 1부터 시작한다고 가정하여 두 숫자의 인덱스를 반환합니다.
4. 합계가 목표값보다 작으면 목표에 도달하기 위해 더 큰 숫자가 필요하므로 다음으로 큰 숫자를 고려하기 위해 왼쪽 포인터를 증가시킵니다.
5. 합계가 목표값보다 크면 목표에 도달하기 위해 더 작은 숫자가 필요하다는 의미이므로 다음으로 작은 숫자를 고려하기 위해 올바른 포인터를 감소시킵니다.
6. 쌍을 찾거나 왼쪽 포인터가 오른쪽 포인터보다 크거나 같아져 쌍이 존재하지 않음을 나타낼 때까지 2-5단계를 반복합니다.
7. 쌍이 발견되지 않으면 빈 배열을 반환합니다.

결론:

"Two Sum II" 문제는 정렬된 배열에서 2포인터 기법을 사용하여 효율적으로 해결됩니다. 두 포인터를 유지하고 합계를 목표값과 비교하면 목표 합계에 합산되는 두 숫자의 인덱스를 찾을 수 있습니다. 이 알고리즘은 배열을 한 번만 순회할 때 O(n)의 시간 복잡도를 갖습니다. 이 접근 방식을 이해하고 구현하면 코딩 인터뷰 및 실제 시나리오에서 유사한 문제를 효율적으로 해결하는 데 도움이 됩니다.