18. 4Sum

Posted on | In |
  • Source : Link
  • Author : Han
  • Date : 2022-02-04

Problems

Given an array nums of n integers, return an array of all the uniquequadruplets [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.

Example 1:

1
2
3
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:

1
2
3
Input: nums = [2,2,2,2,2], target = 8
Output: [[2,2,2,2]]

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
26
27
28
29
30
31
32
33
import java.util.*

class Solution {
    fun fourSum(nums: IntArray, target: Int): List<List<Int>> {
        var res = HashSet<List<Int>>()
        nums.sort()
        for (i in 0..nums.lastIndex - 3) {
            for (j in nums.lastIndex downTo i + 3) {
                var low = i + 1
                var high = j - 1
                val tmp = target - nums[i] - nums[j]
                while (low < high) {
                    val sum = nums[low] + nums[high]
                    when {
                        sum == tmp -> {
                            res.add(listOf(nums[i], nums[low], nums[high], nums[j]))
                            low++
                            high--
                        }
                        sum < tmp -> {
                            low++
                        }
                        else -> {
                            high--
                        }
                    }
                }
            }

        }
        return res.toList()
    }
}