[Multiple pointers] sumZero

Multiple pointers란?

Creating pointers or values that correspond to an index or position and move towards the beginning, end or middle based on a certain condition.

Very efficient for solving problems with minimal space complexity as well.

 

인덱스 또는 위치에 해당하고 특정 조건에 따라 시작, 끝 또는 중간으로 이동하는 포인터 또는 값을 생성합니다.
최소한의 공간 복잡성으로 문제를 해결하는 데에도 매우 효율적입니다. (보통 pair를 찾는데 많이 쓰임)

 

방법

• 2개 reference(i, j)를 갖고, 처음-끝이면 중간으로 가면서 찾게됨. 혹은 왼쪽부터 i,j를 선언하여 같이 오른쪽으로 이동. 어느쪽이던 케이스는 다양하지만 2개의 pointer를 갖게됨
• 정렬된 배열에 잘 쓰임

 

문제: sumZero

Write a function called sumZero which accepts a sorted array of integers. The function should find the first pair where the sum is 0. Return an array that includes both values that sum to zero or undefined if a pair does not exist.

 

정수의 정렬된 배열을 받아들이는 sumZero라는 함수를 작성하십시오. 함수는 합계가 0인 첫 번째 쌍을 찾아야 합니다. 합계가 0이거나 쌍이 존재하지 않는 경우 정의되지 않은 두 값을 모두 포함하는 배열을 반환합니다.

sumZero([-3,-2,-1,0,1,2,3])//[-3,3]
sumZero([-2,0,1,3])//undefined
sumZero([1,2,3])//undefined

 

비효율적 해결

Time complexity - O(N^2)

Space complexity - O(1)

반복문이 2개임, nested loop이 들어가면 길어졌을때 훨씬 반복해야할게 많아짐

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]]
      }
    }
  }
}

sumZero([-3,-2,-1,0,1,2,3])//[-3,3]

multiple pointer를 사용한 해결

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++;
    }
  }
}

sumZero([-3,-2,-1,0,1,2,3])

 

 

While

MDN | While 문

while (condition)
  statement

조건

반복이 시작되기 전에 조건문은 참,거짓을 판단받게 된다. 만약 조건문이 참이라면, while문 안의 문장들이 실행된다. 거짓이라면, 문장은 그냥 while 반복문 후로 넘어간다.

 

문장

조건문이 참일 때만 while문 속의 문장들이 실행된다. 반복문 속에 여러개의 문장을 사용하고 싶다면 중괄호 { } 를 통해 문장들을 하나로 묶어야 한다.

 

 

문제: countUniqueValues

 

implement a function called countUniqueValues, which accepts a sorted array, and counts the unique values in the array. There can be negative numbers in the array, but it will always be sorted.

 

정렬된 배열을 받아들이고 배열의 고유한 값을 계산하는 countUniqueValues라는 함수를 구현합니다. 배열에 음수가 있을 수 있지만 항상 정렬됩니다.

 

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++;
    }
  }
}