# LeetCode – 18. 4Sum

## 法ㄧ: (Time complexity: O(n^4))

``````    func fourSum(_ nums: [Int], _ target: Int) -> [[Int]] {
let sort = nums.sorted()
var result: [[Int]] = []
for i in 0 ..< (nums.count - 3){
for j in (i+1) ..< (nums.count - 2) {
for k in (j+1) ..< (nums.count - 1) {
for l in (k+1) ..< nums.count {
if target == sort[i] + sort[j] + sort[k] + sort[l] {
result.append([sort[i], sort[j], sort[k], sort[l]])
}
}
}
}
}
return result
}
``````

## 法二: Time complexity: O(n^3)

``````func fourSum(_ nums: [Int], _ target: Int) -> [[Int]] {
guard nums.count >= 4 else { return [] }
let sort = nums.sorted()
var resultSet: Set<[Int]> = []
for i in 0 ..< (sort.count - 3) {
for j in (i+1) ..< (sort.count - 2) {
let sum = target - (sort[i] + sort[j])
var left = j + 1
var right = sort.count - 1
while left < right {
if sum == (sort[left] + sort[right]) {
resultSet.insert([sort[i], sort[j], sort[left], sort[right]])
left += 1
right -= 1
} else if sum > (sort[left] + sort[right]) {
left += 1
} else {
right -= 1
}
}
}
}
return resultSet.map { \$0 }
}
``````