15. 3Sum

Posted on | In |
  • Source : Link
  • Author : Han
  • Date : 2022-01-25

Problems

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.

Notice that the solution set must not contain duplicate triplets.

Example 1:

1
2
3
Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]

Example 2:

1
2
3
Input: nums = []
Output: []

Example 3:

1
2
Input: nums = [0]
Output: []

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
fun threeSum(nums: IntArray): List<List<Int>> {
    return nums.toList().findZeroSumTriplets().map { it.value }
}

data class Triple(val value: List<Int>) {
    constructor(first: Int, second: Int, third: Int) :
            this(listOf(first, second, third))
}

fun List<Int>.findZeroSumTriplets(): Set<Triple> = sorted().let {
    val result = HashSet<Triple>()
    0.rangeTo(it.lastIndex - 2).forEach { i ->
        var left = i + 1
        var right = it.lastIndex
        while (left < right) {
            val sum = it[i] + it[left] + it[right]
            when {
                sum == 0 -> result.add(Triple(it[i], it[left++], it[right--]))
                sum < 0  -> left++
                else     -> right--
            }
        }
    }
    return result
}