[leetcode] 15. 3Sum

문제

 

 

풀이

a + b + c = 0 인 경우를 찾는 문제이다.

투 포인터를 이용해서 풀었다.

우선 정렬을 한 다음에 for 루프를 돌면서  nums[index] 가 a 라고 할 때 포인터를 이동하면서 b 와 c 값을 찾았다.

 

문제에서 답에 중복을 허용하지 않기 때문에 중복인 경우는 다시 계산하지 않게 처리했다.

[0, 0, 0, 0, 0, 0] 와 같은 인풋이 들어왔을 때 한 번만 계산하고 스킵하게 된다.

 

시간복잡도는 O(N^2) 이 된다.

=> 정렬하는 데 O(NlogN) +  for 루프 돌면서 b와 c값 찾는 데 O(N^2)

 

 

 

 

코드

fun threeSum(nums: IntArray): List<List<Int>> {
    nums.sort()
    val result: MutableList<List<Int>> = mutableListOf()
    
    for (i in 0 .. nums.lastIndex - 2) {
        if (i > 0 && nums[i] == nums[i - 1]) {
            continue
        }

        var left = i + 1
        var right = nums.lastIndex

        while (left < right) {
            val sum = nums[i] + nums[left] + nums[right]

            when {
                sum < 0 -> {
                    left++
                }
                sum > 0 -> {
                    right--
                }
                sum == 0 -> {
                    result.add(listOf(nums[i], nums[left], nums[right]))
                    while (left < right && nums[left] == nums[left + 1]) left++
                    while (left < right && nums[right] == nums[right - 1]) right--

                    left++
                    right--
                }
            }
        }
    }
    return result
}

 

 

참고

• 15. 3Sum