[LeetCode][Kotlin] 18. 4Sum

18. 4Sum

Given an array nums of n integers, return an array of all the unique quadruplets [nums[a], nums[b], nums[c], nums[d]] such that:

• 0 <= a, b, c, d < n
• a, b, c, and d are distinct.
• nums[a] + nums[b] + nums[c] + nums[d] == target

You may return the answer in any order.

n개의 정수로 구성된 배열 nums가 주어지면 다음과 같은 모든 고유한 사중항 [nums[a], nums[b], nums[c], nums[d]]의 배열을 반환합니다.
- 0 <= a, b, c, d < n 
- a, b, c, d는 서로 다릅니다. 
- nums[a] + nums[b] + nums[c] + nums[d] == target 

답은 어떤 순서로든 반환할 수 있습니다.

 

Example 1:

Input: nums = [1,0,-1,0,-2,2], target = 0

Output: [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

 

Example 2:

Input: nums = [2,2,2,2,2], target = 8

Output: [[2,2,2,2]]

 

Constraints:

• 1 <= nums.length <= 200
• -10^9 <= nums[i] <= 10^9
• -10^9 <= target <= 10^9

---

코드 1

class Solution {
    fun fourSum(nums: IntArray, target: Int): List<List<Int>> {
        nums.sort()

        val answer = mutableListOf<List<Int>>()

        for (i in 0..nums.size - 4) {
            if (i > 0 && nums[i - 1] == nums[i]) {
                continue
            }

            for (j in i + 1..nums.size - 3) {
                if (j > i + 1 && nums[j - 1] == nums[j]) {
                    continue
                }

                var l = j + 1
                var r = nums.lastIndex

                while (l < r) {
                    val sum = nums[i].toLong() + nums[j].toLong() + nums[l].toLong() + nums[r].toLong()

                    if (sum < target) {
                        l++
                    } else if (sum > target) {
                        r--
                    } else {
                        answer.add(listOf(nums[i], nums[j], nums[l], nums[r]))

                        while (l < r && nums[l] == nums[l + 1]) {
                            l++
                        }
                        while (l < r && nums[r - 1] == nums[r]) {
                            r--
                        }

                        l++
                        r--
                    }
                }
            }
        }

        return answer
    }
}

 

코드 2

class Solution {
    fun fourSum(nums: IntArray, target: Int): List<List<Int>> {
        nums.sort()

        val answer = arrayListOf<List<Int>>()
        val arr = arrayListOf<Int>()

        fun dfs(k: Int, start: Int, target: Long) {
            if (k != 2) {
                for (i in start..(nums.size - k)) {
                    if (i > start && nums[i - 1] == nums[i]) {
                        continue
                    }

                    arr.add(nums[i])
                    dfs(k - 1, i + 1, target - nums[i])
                    arr.removeLast()
                }

                return
            }

            var l = start
            var r = nums.lastIndex

            while (l < r) {
                val sum = nums[l].toLong() + nums[r].toLong()
                
                if (sum < target) {
                    l++
                } else if (sum > target) {
                    r--
                } else {
                    answer.add(arr + listOf(nums[l], nums[r]))

                    while (l < r && nums[l] == nums[l + 1]) {
                        l++
                    }
                    while (l < r && nums[r - 1] == nums[r]) {
                        r--
                    }

                    l++
                    r--
                }
            }
        }

        dfs(4, 0, target.toLong())
        return answer
    }
}