LeetCode - The World's Leading Online Programming Learning Platform

Problem

1. input: 정수가 들어있는 배열 nums, 정수 target
2. output: nums에서 3개의 원소를 합하였을 때, target에 가장 가까운 수 리턴
3. 정확히 하나의 답만 존재
   • 3 <= nums.length <= 500
   • 1000 <= nums[i] <= 1000
   • 104 <= target <= 104

Idea

15. 3Sum 문제와 동일한 아이디어 사용

Solution

1. 투포인터 문제로 변환

   • 정수 배열 정렬
   • 시작점 고정하여 투포인터 문제로 변환

   class Solution {
       fun threeSumClosest(nums: IntArray, target: Int): Int {
           var answer = Int.MAX_VALUE
           nums.sort() // 정수 배열 정렬
           for (firstIdx in 0 until nums.size - 2) { // 시작점 고정
               // 투포인터
               var left = firstIdx + 1
               var right = nums.size - 1
               var sum = nums[firstIdx] + nums[left] + nums[right] - target
               while (left < right) {
                   if (sum == 0) {
                       answer = sum
                       left++
                       right--
                   } else  {
                       if (Math.abs(answer) > Math.abs(sum)) answer = sum
                       if (sum < 0) {
                           left++
                       } else {
                           right--
                       }
                   }
                   sum = nums[firstIdx] + nums[left] + nums[right] - target
               }
           }
           return target + answer
       }
   }
   

   시간 복잡도: 배열 순회(시작점 고정) X 배열 순회(투포인터) = n^2

   

Point