두 합 II를 효율적으로 풀기 - 입력 배열이 정렬됨

"Two Sum II - 입력 배열이 정렬됨" 문제는 배열 및 포인터 조작에 대한 이해를 테스트하는 고전적인 코딩 문제입니다. 또한 우아하면서도 효율적인 솔루션을 선보일 수 있는 좋은 기회이기도 합니다. 문제를 자세히 살펴보고 문제 해결을 위한 최적의 접근 방식을 분석해 보겠습니다.

LeetCode 문제 바로가기

문제 설명

내림차순으로 정렬된 1 인덱스 정수 배열이 주어지면, 목표는 그 합이 주어진 목표와 같아지는 두 숫자를 찾는 것입니다. 이 두 숫자의 인덱스를 배열 [index1, index2]로 반환해야 합니다. 여기서 1 <= index1 < index2 <= 숫자.길이. 솔루션은 일정한 추가 공간만 사용해야 합니다.

제약

• 배열 번호는 내림차순으로 정렬되지 않습니다.
• 해결책은 딱 하나입니다.
• 동일한 요소를 두 번 사용할 수 없습니다.
• 입력 배열 길이의 범위는 2~30,000입니다.
• 배열의 값 범위는 -1000부터 1000까지입니다.

입력 및 출력 예

1. 입력: 숫자 = [2,7,11,15], 대상 = 9
   
   출력: [1, 2]

2. 입력: 숫자 = [2,3,4], 대상 = 6
   
   출력: [1, 3]

3. 입력: 숫자 = [-1,0], 대상 = -1
   
   출력: [1, 2]

접근 방식: 두 가지 포인터

문제의 제약 조건(정렬된 배열과 단일 솔루션)으로 인해 이 문제는 2포인터 기술의 완벽한 후보가 됩니다. 이유는 다음과 같습니다.

• 효율성: 두 개의 포인터를 사용하면 단일 패스(O(n) 시간 복잡도)로 배열을 탐색할 수 있습니다.
• 상수 공간: 우리는 보조 데이터 구조를 피하고 지속적인 추가 공간에 대한 문제 요구 사항을 준수합니다.

구현

다음은 두 포인터 접근 방식의 JavaScript 구현입니다.

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {
    const length = nums.length;
    let rightPointer = length - 1;
    let leftPointer = 0;

    while (leftPointer < rightPointer) {
        if (nums[leftPointer] + nums[rightPointer] === target) {
            return [leftPointer + 1, rightPointer + 1];
        }
        if (nums[leftPointer] + nums[rightPointer] > target) {
            rightPointer--;
        } else {
            leftPointer++;
        }
    }
};






  
  
  작동 방식




두 포인터 초기화:



leftPointer는 배열의 시작 부분에서 시작됩니다.

rightPointer는 배열의 끝에서 시작됩니다.



만날 때까지 반복:


leftPointer와 rightPointer에 있는 요소의 합을 계산합니다.
합계가 목표값과 일치하면 1번째 인덱스 위치를 반환합니다.
합계가 목표보다 크면 rightPointer를 감소시켜 합을 줄입니다.
합계가 목표보다 작으면 leftPointer를 증가시켜 합을 늘립니다.



색인 반환:

올바른 쌍을 찾으면 루프가 종료되고 인덱스가 반환됩니다.





  
  
  예제 연습


첫 번째 예를 살펴보겠습니다.



입력: 숫자 = [2, 7, 11, 15], 대상 = 9


초기화: leftPointer = 0, rightPointer = 3




  
  
  반복 단계:



숫자[0] 숫자[3] = 2 15 = 17을 계산합니다. 


너무 크면 rightPointer를 2로 줄입니다.


숫자[0] 숫자[2] = 2 11 = 13을 계산합니다. 


아직 너무 큽니다. rightPointer를 1로 줄입니다.


숫자[0] 숫자[1] = 2 7 = 9를 계산합니다. 


일치 항목을 찾았습니다. [1, 2]를 반환합니다.





  
  
  핵심사항




1-인덱스 조정: 문제는 1 기반 인덱싱을 지정하므로 반환하기 전에 두 포인터에 1을 추가합니다.

에지 사례: 제약 조건은 단일 솔루션을 보장하므로 빈 배열이나 여러 일치 항목을 처리할 필요가 없습니다.

최적화: 2점 접근 방식을 사용하면 O(n) 시간 복잡도와 일정한 공간 요구 사항을 충족할 수 있습니다.



  
  
  결론


2포인터 방법은 입력 배열의 정렬된 특성을 활용하여 "Two Sum II - 입력 배열이 정렬됨" 문제를 우아하게 해결합니다. 이는 효율성을 보장할 뿐만 아니라 공간 제약을 준수하는 강력한 기술이므로 유사한 문제에 대한 접근 방식이 됩니다. 즐거운 코딩하세요!


          

            
        
위 내용은 두 합 II를 효율적으로 풀기 - 입력 배열이 정렬됨의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!