forked from freelf/Algorithm21
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy path3Sum.swift
More file actions
56 lines (53 loc) · 1.54 KB
/
Copy path3Sum.swift
File metadata and controls
56 lines (53 loc) · 1.54 KB
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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
//
// 3Sum.swift
// ConquerAlgorithm
//
// Created by Freelf on 2021/3/12.
// Copyright © 2021 Freelf. All rights reserved.
//
// https://leetcode-cn.com/problems/3sum/
// 15. 三数之和
import Foundation
class ThreeSum {
func threeSum(_ nums: [Int]) -> [[Int]] {
if nums.count < 3 {
return []
}
if nums.count == 3 && nums.reduce(0, { (result, cur) -> Int in
return result + cur
}) == 0{
return [nums]
}
let numSorted = nums.sorted()
var result:[[Int]] = []
if numSorted.first! > 0 || numSorted.last! < 0 {
return []
}
for index in 0 ..< numSorted.count {
if index > 0 && numSorted[index] == numSorted[index - 1] {
continue
}
var L = index + 1
var R = numSorted.count - 1
while L < R {
let sum = numSorted[index] + numSorted[L] + numSorted[R]
if sum == 0 {
result.append([numSorted[index], numSorted[L], numSorted[R]])
while L < R && numSorted[L] == numSorted[L + 1] {
L += 1
}
while L < R && numSorted[R] == numSorted[R - 1] {
R -= 1
}
L += 1
R -= 1
} else if sum < 0 {
L += 1
} else {
R -= 1
}
}
}
return result
}
}