<Medium> 3Sum Closest (LeetCode : C#)

https://leetcode.com/problems/3sum-closest/

📕 문제 설명

정수 배열 nums와 target 값이 주어질 때 합이 target과 가장 가까운 세 정수의 합 반환하기

• Input
  정수 배열 nums, target 값
• Output
  세 정수의 합

예제

풀이

풀이 1.

모든 케이스 탐색

public class Solution {
    public int ThreeSumClosest(int[] nums, int target) {

        int diff = Int32.MaxValue;
        int sum = 0;

        for (int i = 0; i < nums.Length; i++)
        {
            for (int j = i + 1; j < nums.Length; j++)
            {
                for (int k = j + 1; k < nums.Length; k++)
                {
                    int currentSum = nums[i] + nums[j] + nums[k];
                    if (Math.Abs(currentSum - target) < diff)
                    {
                        diff = Math.Abs(currentSum - target);
                        sum = currentSum;
                    }
                }
            }
        }

        return sum;
        
    }
}

풀이 1. 결과

풀이 2.

투 포인터로 가능한 케이스 보기

public class Solution {
    public int ThreeSumClosest(int[] nums, int target) {

        int lp = 0;
        int rp = nums.Length;
        int sum = 0;
        int diff = Int32.MaxValue;
        Array.Sort(nums);

        for (int i = 0; i < nums.Length; i++)
        {
            lp = i + 1;
            rp = nums.Length - 1;

            while (lp < rp)
            {
                int currentSum = nums[i] + nums[lp] + nums[rp];
                if (Math.Abs(currentSum - target) < diff)
                {
                    diff = Math.Abs(currentSum - target);
                    sum = currentSum;

                    while (lp < rp && nums[lp] == nums[lp-1]) lp++;
                }
                else if (currentSum < target) lp++;
                else rp--;
            }
        }

        return sum;
        
    }
}

풀이 2. 결과