LeetCode - 가장 가까운 3Sum

문제 설명

길이가 n인 정수 배열 num과 정수 대상이 주어지면 합계가 대상에 가장 가깝도록 num에서 세 개의 정수를 찾습니다.

세 정수의 합을 반환합니다.

각 입력에 정확히 하나의 솔루션이 있다고 가정할 수 있습니다.

다음에서 가져온 문제 설명: https://leetcode.com/problems/3sum-closest

예 1:

Input: nums = [-1, 2, 1, -4], target = 1
Output: 2
Explanation: The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

예 2:

Input: nums = [0, 0, 0], target = 1
Output: 0

제약:

- 3 <= nums.length <= 1000
- -1000 <= nums[i] <= 1000
- -10^4 <= target <= 10^4

설명

무차별 대입 접근

문제를 해결하기 위한 간단한 접근 방식은 크기 3의 모든 하위 집합을 탐색하고 대상과 이 하위 집합의 합계 간의 차이를 추적하는 것입니다.
그런 다음 sum과 target의 차이가 최소인 부분 집합을 반환합니다.

위 접근 방식의 C++ 구현은 다음과 같습니다.

for (int i = 0; i < arr.size() ; i++)
{
    for(int j =i + 1; j < arr.size(); j++)
    {
        for(int k =j + 1; k < arr.size(); k++)
        {
            //update the closestSum
            if(abs(x - closestSum) > abs(x - (arr[i] + arr[j] + arr[k])))
                closestSum = (arr[i] + arr[j] + arr[k]);
        }
    }
}

return closestSum

세 개의 중첩 루프를 사용하기 때문에 위 접근 방식의 시간 복잡도는 O(N^3)이고 추가 공간이 필요하지 않습니다. 공간 복잡도는 O(1)입니다.

두 포인터 기술

배열을 정렬함으로써 알고리즘의 효율성을 향상시킬 수 있습니다. 배열이 정렬되면 두 포인터 기술을 사용할 수 있습니다.

배열을 탐색하고 트리플렛의 첫 번째 요소를 수정합니다. 목표에 가장 가까운 숫자인 nums[i]를 찾기 위해 두 포인터 알고리즘을 사용합니다. 가장 가까운 합계를 업데이트합니다.
두 포인터는 선형 시간이 걸리므로 중첩 루프보다 낫습니다.


연산

- if nums.size < 3
  - return 0

- sort(nums.begin(), nums.end())

- set i = 0, minDiff = INT_MAX
- initialize sum

- loop while i < nums.size() - 2
  - set left = i + 1
  - set right = nums.size() - 1

  - loop while right > left
    - set temp = nums[i] + nums[left] + nums[right]
    - set diff = abs(temp - target)

    - if diff == 0
      - return target

    - if diff < minDiff
      - minDiff = diff
      - sum = temp

    - if temp < target
      - left++
    - else
      - right++

  - loop end

  - i++
- loop end

- return sum

C++ 솔루션

class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
        if(nums.size() < 3){
            return 0;
        }

        sort(nums.begin(), nums.end());

        int i = 0;
        int sum, minDiff = INT_MAX;

        while(i < nums.size() - 2){
            int left = i + 1;
            int right = nums.size() - 1;
            while(right > left){
                int temp = nums[i] + nums[left] + nums[right];
                int diff = abs(temp - target);

                if(diff == 0){
                    return target;
                }

                if(diff < minDiff){
                    minDiff = diff;
                    sum = temp;
                }

                if(temp < target){
                    left++;
                }
                else{
                    right--;
                }
            }
            i++;
        }

    return sum;
  }
};

골랑 솔루션

const MaxUint = ^uint(0)
const MaxInt = int(MaxUint >> 1)

func absInt(x int) int{
    if x < 0 {
        return x*-1
    }

    return x
}

func threeSumClosest(nums []int, target int) int {
    numsLength := len(nums)
    if numsLength < 3 {
        return 0
    }

    sort.Ints(nums)

    i, sum := 0, 0
    minDiff := MaxInt

    for i < numsLength - 2 {
        left := i + 1
        right := numsLength - 1

        for right > left {
            temp := nums[i] + nums[left] + nums[right]
            diff := absInt(temp - target)

            if diff == 0 {
                return target
            }

            if diff < minDiff {
                minDiff = diff
                sum = temp
            }

            if temp < target {
                left++
            } else {
                right--
            }
        }

        i++
    }

    return sum
}

자바스크립트 솔루션

var threeSumClosest = function(nums, target) {
    if(nums.length < 3) {
        return 0;
    }

    nums.sort();

    let i = 0, minDiff = Number.MAX_VALUE;
    let sum;

    while( i < nums.length - 2 ){
        let left = i + 1;
        let right = nums.length - 1

        while( right > left ){
            let temp = nums[i] + nums[left] + nums[right];
            let diff = Math.abs(temp - target);

            if( diff == 0 ){
                return target;
            }

            if( diff < minDiff ){
                minDiff = diff;
                sum = temp;
            }

            if( temp < target ){
                left++;
            } else {
                right--;
            }
        }
        i++;
    }

    return sum;
};

솔루션이 어떻게 작동하는지 확인하기 위해 알고리즘을 테스트 실행해 보겠습니다.

Input: nums = [-1, 2, 1, -4], target = 1

Step 1: if nums.size() < 3
           4 < 3
           false

Step 2: sort(nums.start(), nums.end())
          - [-4, -1, 1, 2]

Step 3: int i = 0;
        int sum, minDiff = INT_MAX;

Step 4: loop while i < nums.size() - 2
        0 < 4 - 2
        0 < 2
        true

        left = i + 1
             = 0 + 1
             = 1
        right = nums.size() - 1
              = 4 - 1
              = 3

        loop while right > left
        3 > 1
        true

        temp = nums[i] + nums[left] + nums[right]
             = nums[0] + nums[1] + nums[3]
             = -4 + -1 + 2
             = -3

        diff = abs(temp - target)
             = abs(-3 - 1)
             = abs(-4)
             = 4

        if diff == 0
           4 == 0
           false

        if diff < minDiff
           4 < INT_MAX
           true

           minDiff = diff
                   = 4
           sum = temp
               = -3

        if temp < target
           -3 < 4
           true

           left++
           left = 2

        loop while right > left
        3 > 2
        true

        temp = nums[i] + nums[left] + nums[right]
             = nums[0] + nums[2] + nums[3]
             = -4 + 1 + 2
             = -1

        diff = abs(temp - target)
             = abs(-1 - 1)
             = abs(-2)
             = 2

        if diff == 0
           2 == 0
           false

        if diff < minDiff
           2 < 4
           true

           minDiff = diff
                   = 2
           sum = temp
               = -1

        if temp < target
           -1 < 4
           true

           left++
           left = 3

        loop while right > left
        3 > 3
        false

        i++
        i = 1

Step 5: loop while i < nums.size() - 2
        1 < 4 - 2
        1 < 2
        true

        left = i + 1
             = 1 + 1
             = 2
        right = nums.size() - 1
              = 4 - 1
              = 3

        loop while right > left
        3 > 2
        true

        temp = nums[i] + nums[left] + nums[right]
             = nums[1] + nums[2] + nums[3]
             = -1 + 1 + 2
             = 2

        diff = abs(temp - target)
             = abs(2 - 1)
             = abs(1)
             = 1

        if diff == 0
           1 == 0
           false

        if diff < minDiff
           1 < 2
           true

           minDiff = diff
                   = 1
           sum = temp
               = 2

        if temp < target
           2 < 4
           true

           left++
           left = 3

        loop while right > left
        3 > 3
        false

        i++
        i = 2

Step 6: loop while i < nums.size() - 2
        2 < 4 - 2
        2 < 2
        false

Step 7: return sum
        return 2

So the answer is 2.