LeetCode 15. 3Sum

LeetCode Notes [37]

Problem

3Sum - LeetCode

Intuition

The idea is to reduce the 3Sum problem into a Two Sum problem. Given the sum of two numbers, the third number must be the negative of the given sum. Therefore, the target for each two sum is the negative number of each array elements.

Implementation

class Solution {
    private lateinit var map: MutableMap<Int, Int>

    fun threeSum(nums: IntArray): List<List<Int>> {
        map = mutableMapOf()
        nums.forEachIndexed { index, num ->
            map[num] = index
        }
        val result = mutableSetOf<List<Int>>()
        for (i in nums.indices) {
            val target = -nums[i]
            for (j in i + 1 until nums.size) {
                val num = nums[j]
                val remains = target - num
                val k = map[remains]
                k?.let { 
                    if (k != i && k > j) {
                        result.add(listOf(-target, num, remains).sorted())
                    }
                }
            }
        }
        return result.toList()
    }
}

Complexity Analysis

• Time Complexity: O(n²)
• Space Complexity: O(n)