[알고리즘] 다중 포인터

문제

배열에 연속한 둘을 더해 0이 되는값이 있다면 그 두값을 return하는 함수를 만든다.

배열의 요소들은 오름차순으로 정렬되어있다.

예시

sumZero([-4, -3, -2, -1, 0, 1, 2, 5]);

 

풀이

(1) 1번풀이

function sumZero(arr) {
  for (let i = 0; i < arr.length; i++) {
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[i] + arr[j] === 0) {
        return [arr[i], arr[j]];
      }
    }
  }
}

2중 for문을 돌려 시간복잡도가 O(n^2)이다.

 

(2) 2번풀이

function sumZero(arr) {
  let left = 0;
  let right = arr.length - 1;
  while (left < right) {
    let sum = arr[left] + arr[right];
    if (sum === 0) {
      return [arr[left], arr[right]];
    } else if (sum > 0) {
      right--;
    } else {
      left++;
    }
  }
}

반복문을 한번만 돌려 시간복잡도 O(n)

포인터 두개를 이용해서 풀이