목표에 근접한 삼중 항 합계

5891 단어 javascriptleetcode
정렬되지 않은 정수 배열 a와 대상이 주어지면 합계가 대상 값에 가장 가까운 배열에서 세 쌍을 찾습니다. 삼중항의 합을 반환합니다.

예 1:

입력: a[] = [-2, -4, 6, 3, 7], 대상 = 2
출력: 1
설명: 목표에 가장 근접한 합을 갖는 삼중항은 [-2, -4, 7]이고 삼중항의 합 = 1
예 2:

입력: a[] = [10, 2, 30, 49, 8], 대상 = 50
출력: 48
설명: 목표에 가장 가까운 합을 갖는 삼중항은 [10, 30, 8], 삼중항의 합 = 48

const threeSum = (arr, x) => {
  let nums = [...arr].sort();

  let smallestDiff = Number.MAX_VALUE;
  for (let i = 0; i < nums.length - 2; i++) {
    if (i > 0 && nums[i] === nums[i - 1]) {
      continue;
    }

    let j = i + 1;
    let k = nums.length - 1;

    while (k > j) {
      let sum = nums[i] + nums[j] + nums[k];
      let currentDiff = x - sum;

      if (currentDiff == 0) {
        return sum;
      }

      if (Math.abs(currentDiff) < Math.abs(smallestDiff)) {
        smallestDiff = currentDiff;
      }

      if (currentDiff > 0) {
        j++;
      } else {
        k--;
      }
    }
  }
  console.log(x - smallestDiff);
  return x - smallestDiff;
};

threeSum([10, 2, 30, 49, 8], 50);
threeSum([1, 0, 1, 1], 100);

좋은 웹페이지 즐겨찾기