LeetCode: 18. 4Sum

LeetCode: 18. 4Sum

Problem: 18. 4Sum

Link: https://leetcode.com/problems/4sum/

Difficulty: Medium

Description:

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.

Note: The solution set must not contain duplicate quadruplets.

Example:

Given array nums = [1, 0, -1, 0, -2, 2], and target = 0.

A solution set is:[[-1, 0, 0, 1],[-2, -1, 1, 2],[-2, 0, 0, 2] ]

Solution:

Language: Swift

Runtime: 32ms
Memory: 18.9MB

Copy to Clipboard

class Solution {
    func fourSum(_ nums: [Int], _ target: Int) -> [[Int]] {
        if nums.count < 4 {
            return []
        }
        
        let nums = nums.sorted()
        var result : [[Int]] = []
        
        for i in 0 ..< nums.count - 3 {
            if nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target {
                    break
                }
            
            if nums[i] + nums[nums.count - 1] + nums[nums.count - 2] + nums[nums.count - 3] < target {
                continue
            }
            
            if i > 0 && nums[i] == nums[i - 1] {
                continue
            }
            
            for j in i + 1 ..< nums.count - 2 {
                if 3 * nums[j] > target - nums[i] {
                    break
                }
                
                if nums[j] + nums[nums.count - 1] + nums[nums.count - 2] < target - nums[i] {
                    continue
                }
                
                if j > i + 1 && nums[j] == nums[j - 1] {
                    continue
                }
                
                var left = j + 1
                var right = nums.count - 1

while left < right {
                    let sum = nums[i] + nums[j] + nums[left] + nums[right]
                    
                    if sum == target {
                        result.append([nums[i], nums[j], nums[left], nums[right]])
                        left += 1
                        right -= 1
                        
                        while nums[right] == nums[right + 1] && left < right {
                            right -= 1
                        }
                        
                        while nums[left]  == nums[left - 1] && left < right {
                            left += 1
                        }
                    } else if sum > target {
                        right -= 1
                    } else {
                        left += 1
                    }
                }
            }
        }
        return result
    }
}

Related Posts

Leave A Comment Cancel reply