LeetCode 15. 3Сумма

Примечания LeetCode [37]

Проблема

Интуиция

Идея состоит в том, чтобы свести задачу 3Sum к задаче Две суммы. Учитывая сумму двух чисел, третье число должно быть отрицательным от данной суммы. Следовательно, целью для каждой суммы двух является отрицательное число каждого элемента массива.

Выполнение

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()
    }
}

Анализ сложности

• Временная сложность: O(n²)
• Сложность пространства: O(n)