class Solution {
    fun threeSum(nums: IntArray): List<List<Int>> {
        val ans = mutableListOf<List<Int>>()
        
        nums.sort()
        
        var target: Int
        var left: Int
        var right: Int
        var sum: Int
        
        for(i in nums.indices) {
            if (i == 0 || (nums[i] <= 0 && nums[i] != nums[i-1])) {
                target = -nums[i]
                
                left = i + 1
                right = nums.lastIndex
                
                while (left < right) {
                    sum = nums[left] + nums[right]
                    
                    if (sum == target) {
                        ans.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
                        }
                    } else if (sum < target) {
                        ++left
                    } else {
                        --right
                    }
                }
            }
        }
        
        return ans
    }
}