9.LeetCode刷题For Swift·18. 4Sum 四

1、原题

Given an array nums of n integers and an integer target, are there elements a, b, c, and d in nums such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.
Notice that the solution set must not contain duplicate quadruplets.

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 = [], target = 0
Output: []

2、思路

3、代码

class Solution {
    func fourSum(_ nums: [Int], _ target: Int) -> [[Int]] {
        // 和三数之和是同类型，使用双指针法
        let nums = nums.sorted()
        var result = [[Int]]()
        for i in 0..<nums.count {
            /*
             // 这里不能使用这个，因为target的值不确定
            if newNums[i] > target {
                return result
            }
            */
            if i > 0 && nums[i] == nums[i-1] {
                continue
            }
            for j in i+1..<nums.count {
                if j > i+1 && nums[j] == nums[j-1] {
                    continue
                }
                var left = j + 1
                var right = nums.count - 1
                while left < right {
                    if nums[i] + nums[j] + nums[left] + nums[right] > target {
                        right -= 1
                    } else if nums[i] + nums[j] + nums[left] + nums[right] < target {
                        left += 1
                    } else {
                        result.append([nums[i], nums[j], nums[left], nums[right]])
                        // 去重
                        while left < right && nums[right] == nums[right - 1] {
                            right -= 1
                        }
                        while left > right && nums[left] == nums[left + 1] {
                            left += 1
                        }
                        // 找到后，双指针内缩
                        right -= 1
                        left += 1
                    }
                }
            }
        }
        return result
    }
}