[LeetCod] 3Sum - kotlin

class Solution {
    fun threeSum(nums: IntArray): List<List<Int>> {
        nums.sort()
        val len = nums.size
        val result: MutableList<List<Int>> = ArrayList()
        var l: Int
        var r: Int
        var i = 0
        while (i < len - 2) {
            l = i + 1
            r = len - 1
            while (r > l) {
                val sum = nums[i] + nums[l] + nums[r]
                if (sum < 0) {
                    l++
                } else if (sum > 0) {
                    r--
                } else {
                    val list: MutableList<Int> = ArrayList()
                    list.add(nums[i])
                    list.add(nums[l])
                    list.add(nums[r])
                    result.add(list)
                    while (l < r && nums[l + 1] == nums[l]) {
                        l++
                    }
                    while (r > l && nums[r - 1] == nums[r]) {
                        r--
                    }
                    l++
                    r--
                }
            }
            while (i < len - 1 && nums[i + 1] == nums[i]) {
                i++
            }
            i++
        }
        return result
    }
}

 

시간 복잡도: O(N²)

 - 바깥쪽 루프(고정되는 i)가 O(N)번, 내부 투 포인터 이동이 평균적으로 O(N) 정도로 동작하므로 총합은 O(N²)입니다.

 

1. 바깥쪽 루프 (고정되는 i)에 대한 분석

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

• 배열의 길이를 N이라고 할 때, i는 0부터 N-3까지 반복합니다.

• 즉, 바깥쪽 반복문이 최대 (N-2)회 수행되므로, 이 부분만 놓고 보면 대략 O(N) 정도의 반복입니다.

 

2. 내부 루프 (투 포인터 탐색)에 대한 분석

고정된 i에 대해, 나머지 구간 i+1부터 N-1 사이를 **왼쪽 포인터 l**와 **오른쪽 포인터 r**로 탐색합니다.

var l = i + 1
var r = nums.size - 1
while (l < r) {
    val sum = nums[i] + nums[l] + nums[r]
    when {
        sum < 0 -> l++
        sum > 0 -> r--
        else -> {
            // 0인 경우 결과 저장, 중복 제거 후 l++, r--
        }
    }
}

 

• 이 구간의 길이는 대략 N - (i+1) 정도입니다.

• 포인터 l와 r은 각 단계마다 최소 한 칸씩 움직이며, 일반적으로 한 바퀴 검색이 끝나기까지 최대 O(N)번 이동하게 됩니다.

• 예: l가 왼쪽에서 시작해 오른쪽으로 이동하고, r가 오른쪽에서 시작해 왼쪽으로 이동하며, 두 포인터가 만날 때까지 각 단계에서 포인터가 1씩 이동.

• 따라서 내부 투 포인터 로직은, 고정된 i에 대해 대략 O(N) 시간 안에 모든 경우를 살펴볼 수 있습니다.

 

3. 전체 알고리즘의 시간 복잡도

• 바깥쪽 루프: O(N)

• 내부 투 포인터 탐색: O(N)

 

• 두 단계를 곱하면 O(N) × O(N) = O(N²).

 

공간 복잡도

 - O(N) 이하 (결과를 저장하는 공간 + 정렬 공간)

 

중복 제거 방법

 - 첫 번째 수(i)가 이전과 같다면 스킵

 - 투 포인터를 옮길 때도, 같은 수를 반복해서 만나면 추가로 이동하여 똑같은 조합을 만들지 않도록 처리