home

    23-11-08

    (알고리즘) 투포인터 with JavaScript

    투포인터를 자바스크립트로 구현해보자.

    투포인터란?

    two-pointer

    투 포인터(Two Pointers)는 두 개의 포인터를 이용하여 배열 또는 리스트를 탐색하는 알고리즘이다. 보통 배열의 왼쪽 끝과 오른쪽 끝을 가리키는 두 개의 포인터를 이용하여 구현한다. 배열이 정렬 돼 있을 때 사용하면 좋은 알고리즘이다.

    위의 이미지를 자바스크립트 코드로 나타내보자.

    function twoSum(nums, target) {
      let left = 0;
      let right = nums.length - 1;
      
      while (left < right) {
        const sum = nums[left] + nums[right];
        
        if (sum === target) {
          return [left, right];
        } else if (sum <br target) {
          left++;
        } else {
          right--;
        }
      }
      
      return [];
     
    }
    const nums = [1, 5, 8, 10, 13, 16, 27, 32, 45, 60];
    const target = 40;
     
    const result = twoSum(nums, target);
    console.log(result); //  [2, 7]
    • left와 right로 배열의 양 끝을 저장해준다
    • left와 right를 더해서 sum이란 변수를 만들어준다
    • sum이 target보다 작으면 left를 오른쪽으로 이동
    • sum이 target보다 크면 right를 왼쪽으로 이동
    • sum이 target과 같으면 값을 리턴해준다.

    이미지 출처
    https://tarunjain07.medium.com/two-pointers-notes-4d1400357437