문제

Given an array of unsorted numbers and a target number, find a triplet in the array whose sum is as close to the target number as possible, return the sum of the triplet. If there are more than one such triplet, return the sum of the triplet with the smallest sum.

input & output

Example 1

Input: [-2, 0, 1, 2], target=2
Output: 1

Explanation: The triplet [-2, 1, 2] has the closest sum to the target.

Example 2

Input: [-3, -1, 1, 2], target=1
Output: 0

Explanation: The triplet [-3, 1, 2] has the closest sum to the target.

Example 3

Input: [1, 0, 1, 1], target=100
Output: 3

Explanation: The triplet [1, 1, 1] has the closest sum to the target.

---

Approach #1

      -2 0 1 2
i      ^
left     ^
right      ^

i, left, right를 이동시키며 tripletSum을 구하고,
target-합의 절댓값을 비교하며 closestSum을 갱신해준다.

Solution #1

function findClosestSum(input, targetNum){
  let closestSum = Number.MAX_VALUE;
  input.sort((a,b)=>a-b);
  
  for(let i =0; i<input.length; i++){
      let left = i+1;
      let right = left+1;
      while(left<input.length){
         if(right === input.length){
            left++; 
            right = left+1;
         }
         if(left === input.length-1) break;

         let sum = input[i]+input[left]+input[right]; //0
         if(Math.abs(targetNum - closestSum) > Math.abs(targetNum - sum)) closestSum = sum; //1
         //console.log(closestSum)
         right++;
      }
	}
	return closestSum;
}

Time Complexity

O(NlogN)+O(N^2)

N: input.length
input 배열을 정렬하는데 NlogN, for문에서 i, while문에서 left, right 이동시키며 sum 확인하는것에서 N^2.

Space Complexity

O(1)

함수 내에서 연산을 위한 추가적인 공간 할당하지 않으므로 O(1).

---

Approach #2

      -2 0 1 2
i      ^
left     ^
right        ^

i, left, right를 이동시키며 tripletSum을 구하고,
target-합의 절댓값을 비교하며 closestSum을 갱신해준다.
solution 1과 다른점은 left, right 갱신시 target과 curSum을 비교한다는 점이다.
target보다 curSum이 작으면 left를 증가시켜주고, target이 curSum보다 크면 right를 감소시킨다.

Solution #2

function tripletSum(input, targetNum){
   // edge case
   if(input.length < 3) return null;

   input.sort((a,b) => a-b);

   let closestSum = null;
   let closestGap = null;

   for(let i=0; i<input.length-2; i++) {
      let left = i+1;
      let right = input.length - 1;
      
      if(i===0) {
         closestSum = input[i] + input[left] + input[right];
         closestGap = Math.abs(targetNum - closestSum);
      }

      while(left < right) {
         let curTarget = targetNum - input[i];
         let curSum = input[i] + input[left] + input[right];
         let curGap = Math.abs(targetNum - curSum);
         
         if(closestGap > curGap || (closestGap === curGap) && (closestSum > curSum)){
            closestSum = curSum;
            closestGap = curGap;
         }

         if(targetNum > curSum) left++;
         else right--;
      }
   }
   return closestSum;
}

Time Complexity

O(NlogN)+O(N^2)

N: input.length
input 배열을 정렬하는데 NlogN, for문에서 i, while문에서 left, right 이동시키며 sum 확인하는것에서 N^2.

Space Complexity

O(1)

함수 내에서 연산을 위한 추가적인 공간 할당하지 않으므로 O(1).

---