다중 포인터 & 기준점 간 이동 배열 패턴

다중 포인터

더 하면 0이 되는 쌍을 찾아라

입출력 예시

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

countUniqueValues([1,1,1,1,1,2]) // 2
countUniqueValues([1,2,3,4,4,4,7,7,12,12,13]) // 7
countUniqueValues([]) // 0
countUniqueValues([-2,-1,-1,0,1]) // 4

첫번째 솔루션

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

• Time Complexity - O(N^2)
• Space Complexity - O(1)

두번째 솔루션

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

• Time Complexity - O(N)
• Space Complexity - O(1)

기준점 간 이동 배열 패턴

입출력 예시

maxSubarraySum([1,2,5,2,8,1,5],2) // 10
maxSubarraySum([1,2,5,2,8,1,5],4) // 17
maxSubarraySum([4,2,1,6],1) // 6
maxSubarraySum([4,2,1,6,2],4) // 13
maxSubarraySum([],4) // null

첫번째 인자: 배열
두번째 인자: 묶을 갯수

maxSubarraySum([1,2,5,2,8,1,5],2)
2개씩 묶어서 가장 큰 합의 결과

첫번째 솔루션

function maxSubarraySum(arr, num) {
  if (num > arr.length){
    return null;
  }
  var max = -Infinity;
  for (let i = 0; i < arr.length - num + 1; i ++){
    temp = 0;
    for (let j = 0; j < num; j++){
      temp += arr[i + j];
    }
    if (temp > max) {
      max = temp;
    }
  }
  return max;
}

• Time Complexity - O(N^2)

두번째 솔루션

function maxSubarraySum(arr, num){
  let maxSum = 0;
  let tempSum = 0;
  if (arr.length < num) return null;
  for (let i = 0; i < num; i++) {
    maxSum += arr[i];
  }
  tempSum = maxSum;
  for (let i = num; i < arr.length; i++) {
    tempSum = tempSum - arr[i - num] + arr[i];
    maxSum = Math.max(maxSum, tempSum);
  }
  return maxSum;
}

• Time Complexity - O(N)

i를 앞의 숫자, j를 비교할 숫자라는 기준

i를 처음부터 끝까지 도는데
j를 i마다 반복해서 시간복잡도를 O(N^2)까지 높이는 것 대신
j의 인덱스를 추가하며 i의 인덱스를 하나씩 앞으로 옮기는 것으로 한번만 순회하는 O(N)으로 복잡도를 낮출 수 있다.