Leetcode.com/problems/4s…

Discuss:www.cnblogs.com/grandyang/p…

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.

Example 1:

Input: nums = (1, 0, 1, 0, 2, 2], the Output target = 0: [[,1,2-2-1], [2,0,0,2], [1,0,0,1]]Copy the code

Example 2:

Input: nums =,2,2,2,2 [2], the Output target = 8: [,2,2,2 [2]]Copy the code

Constraints:

  • 1 <= nums.length <= 200

  • -109 <= nums[i] <= 109

  • -109 <= target <= 109

Solution a:

This problem is similar to Three Sum, except that there is an extra layer of loop, which can be repeated manually. There are three main things you can do. First, you can put one in each of the two for loops, because once the current number is the same as the number above, it will definitely repeat. Then, when sum equals target, after adding four numbers to the result res, both left and right need to be repeated, traversing the left and right directions respectively.

class Solution {
    fun fourSum(nums: IntArray, target: Int): List<List<Int> > {if (nums.size < 4) {
            return mutableListOf()
        }
        val result = mutableListOf<List<Int>>()
        nums.sort()
        for (i in 0..nums.size - 4) {
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue
            }
            for (j in i + 1..nums.size - 3) {
                if (j > i + 1 && nums[j] == nums[j - 1]) {
                    continue
                }
                var left = j + 1
                var right = nums.size - 1
                while (left < right) {
                    val sum = nums[i] + nums[j] + nums[left] + nums[right]
                    if (sum == target) {
                        val item = mutableListOf(nums[i], nums[j], nums[left], nums[right])
                        result.add(item)
                        while (left < right && nums[left] == nums[left + 1]) {
                            ++left
                        }
                        while (left < right && nums[right] == nums[right - 1]) {
                            --right
                        }
                        ++left
                        --right
                    } else if (sum < target) {
                        ++left
                    } else {
                        --right
                    }
                }
            }
        }
        return result
    }
}
Copy the code