Daily LeetCode Challenge - 15. 3Sum

Problem From.
https://leetcode.com/problems/3sum/

오늘 문제는 nums array 가 주어질때, 서로 다른 세 위치의 수를 더해서 0 이되는 경우를 쌍을 구하는 문제였다.

이 문제는 먼저 nums 를 앞에서부터 하나씩 검사해나가며, 각 경우에 binary search 를 사용하여 target 을 구하면 되었다. target 은 nums 를 검사해나가는 수의 음수로 정해둔다. 그렇게 하면 세 수를 더해서 0을 만드는 경우를 계산하기 쉬워진다.
(-target) + start + end = 0 이런식으로 계산을 할 수 있다.

class Solution {
    fun threeSum(nums: IntArray): List<List<Int>> {

        nums.sort()

        val answer = mutableSetOf<List<Int>>()

        for(i in 0 until nums.size - 2) {

            val target = -nums[i]
            var start = i+1
            var end = nums.size - 1
            while(start < end) {
                when {
                    target > nums[start] + nums[end] -> {
                        start += 1
                    }
                    target == nums[start] + nums[end] -> {
                        answer.add(listOf(nums[i], nums[start], nums[end]))
                        start += 1
                    }
                    target < nums[start] + nums[end] -> {
                        end -= 1
                    }
                }
            }

        }

        return answer.toList()
    }
}