[Swift]LeetCode15.三数之和|3Sum

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› 移动开发›Swift 教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址：https://www.cnblogs.com/strengthen/p/9884470.html
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎，请直接点击！！！

进入博主App Store主页，下载使用各个作品！！！

注：博主将坚持每月上线一个新app！！！

Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note:

The solution set must not contain duplicate triplets.

Example:

Given array nums = [-1, 0, 1, 2, -1, -4],
A solution set is:
[
  [-1, 0, 1],
  [-1, -1, 2]
]

给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。

注意：答案中不可以包含重复的三元组。

例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4]，

满足要求的三元组集合为：
[
  [-1, 0, 1],
  [-1, -1, 2]
]

116ms

 1 class Solution {
 2     func threeSum(_ nums: [Int]) -> [[Int]] {
 3         guard nums.count > 2 else { return [] }
 4         var solutions = [[Int]]();
 5         let sorted = nums.sorted() { $0 < $1 }
 6         let count = sorted.count
 7         var i = 0
 8         
 9         while (i < count - 2) {
10             if (i == 0 || (i > 0 && sorted[i] != sorted[i - 1])) {
11                 var left = i + 1
12                 var right = count - 1
13                 let num = sorted[i]
14                 
15                 while (left < right) {
16                     let currentSum = sorted[left] + sorted[right] + num
17                     
18                     if (currentSum == 0) {
19                         solutions.append([sorted[left], sorted[right], num])
20                         
21                         while (left < right && sorted[left] == sorted[left + 1]) {
22                             left += 1
23                         }
24                         
25                         while (left < right && sorted[right] == sorted[right - 1]) {
26                             right -= 1
27                         }
28                         left += 1
29                         right -= 1
30                     } else if (currentSum < 0) {
31                         left += 1
32                     } else {
33                         right -= 1
34                     }
35                 }
36             }
37             
38             i += 1
39         }
40         
41         return solutions
42     }
43 }

120ms

 1 class Solution {
 2     func threeSum(_ nums: [Int]) -> [[Int]] {
 3     guard nums.count > 2 else {
 4         return []
 5     }
 6 
 7     var results = [[Int]]()
 8     let sortedNums = nums.sorted()
 9 
10     for i in 0..<sortedNums.count-1 {
11         if i > 0 && sortedNums[i] == sortedNums[i-1] {
12             continue
13         }
14         let target = 0 - sortedNums[i]
15         var low = i + 1
16         var high = nums.count - 1
17 
18         while low < high {
19             let sum = sortedNums[low] + sortedNums[high]
20             if sum == target {
21                 let result = [sortedNums[i], sortedNums[low], sortedNums[high]]
22                 results.append(result)
23 
24                 while (low < high && sortedNums[low] == sortedNums[low+1]) {
25                     low += 1
26                 }
27                 while (low < high && sortedNums[high] == sortedNums[high-1]) {
28                     high -= 1
29                 }
30                 low += 1
31                 high -= 1
32             } else if sum < target {
33                 low += 1
34             } else {
35                 high -= 1
36             }
37         }
38     }
39 
40     return results
41 }
42 }

124ms

 1 class Solution {
 2     func threeSum(_ nums: [Int]) -> [[Int]] {
 3         if nums.count < 3 {
 4             return []
 5         }
 6         
 7         var result = [[Int]]()
 8         var snums = nums.sorted()
 9         
10         for i in 0...snums.count-2 {
11             if i > 0 && snums[i] == snums[i-1] {
12                 continue
13             }
14             
15             var l = i + 1
16             var r = snums.count - 1
17             
18             while l < r {
19                 let s = snums[i] + snums[l] + snums[r]
20                 
21                 if s == 0 {
22                     result.append([snums[i], snums[l], snums[r]])
23                     l += 1
24                     r -= 1
25                     
26                     while l < r && snums[l] == snums[l-1] {
27                         l += 1
28                     }
29                     
30                     while l < r && snums[r] == snums[r+1] {
31                         r -= 1
32                     }
33                 } else if s < 0 {
34                     l += 1
35                 } else {
36                     r -= 1
37                 }
38             }
39         }
40         
41         return result
42     }
43 }

136ms

 1 class Solution {
 2     func threeSum(_ nums: [Int]) -> [[Int]] {
 3         var nums = nums.sorted()
 4         var result = [[Int]]()
 5         
 6         for i in 0..<nums.count {
 7             if i == 0 || i > 0 && nums[i] != nums[i-1] {
 8                 var left = i + 1, right = nums.count - 1
 9                 var sum = 0 - nums[i]
10                 print(sum)
11                 while left < right {
12                    if nums[left] + nums[right] == sum {
13                        result.append([nums[left], nums[right], nums[i]])
14                        while left < right && nums[left] == nums[left + 1]{
15                                left += 1
16                        }
17                         while left < right && nums[right] == nums[right - 1]{
18                                right -= 1
19                        }
20                        left += 1
21                        right -= 1
22                    } else if nums[left] + nums[right] < sum {
23                        left += 1
24                    } else {
25                        right -= 1
26                    }
27                 }   
28             }
29         }
30         return result
31     }
32 }

148ms

 1 import Foundation
 2 class Solution {
 3     func threeSum(_ nums: [Int]) -> [[Int]] {
 4         
 5         var n = nums
 6         n.sort()
 7         
 8         var aIndex1: Int = 0
 9         var aIndexLow: Int = 0
10         var aIndexHi: Int = 0
11         
12         var aResult = [[Int]]()
13         
14         var aTargetSum: Int = 0
15         
16         while aIndex1 < (n.count - 2) {
17             
18             //The sandwich principle.
19             aIndexLow = aIndex1 + 1
20             aIndexHi = n.count - 1
21             
22             while (aIndexLow < aIndexHi) && (n[aIndex1] + n[aIndexLow]) <= aTargetSum {
23                 
24                 var aSum = n[aIndex1] + n[aIndexLow] + n[aIndexHi]
25                 if aSum == aTargetSum {
26                     var aArr = [n[aIndex1], n[aIndexLow], n[aIndexHi]]
27                     aResult.append(aArr)
28                     
29                     aIndexHi -= 1
30                     //Prevent dupes on hi
31                     while aIndexLow < aIndexHi && n[aIndexHi + 1] == n[aIndexHi] {
32                         aIndexHi -= 1
33                     }
34                     
35                     //Prevent dupes on low
36                     aIndexLow += 1
37                     while aIndexLow < aIndexHi && n[aIndexLow - 1] == n[aIndexLow] {
38                         aIndexLow += 1
39                     }  
40                 } else if aSum > aTargetSum {
41                     aIndexHi -= 1
42                 } else {
43                     aIndexLow += 1   
44                 }
45             }
46             
47             //prevent dupes with first index.
48             aIndex1 += 1
49             while aIndex1 < n.count && n[aIndex1 - 1] == n[aIndex1] {
50                 aIndex1 += 1
51             }
52         }
53         
54         return aResult
55     }
56 }

164ms

 1 class Solution {
 2     func twoSum(_ array: [Int], ignoreIndex i: Int, result: inout [[Int]]) {
 3         
 4         var l = i + 1
 5         
 6         let a = array[i]
 7         
 8         var r = array.count - 1
 9         
10         if i > 0 && a == array[i - 1] {
11             return 
12         }
13         
14         while l < r {
15             
16             let b = array[l]
17         
18             if a + b > 0 {
19                 return  
20             }
21             
22             let c = array[r]
23             
24             var sum = a + b + c
25             
26             if sum == 0 {
27                 let indexes = [a, b, c]
28                 
29                 result.append(indexes)
30                 
31                 l += 1
32                                 
33                 while l < r && array[l] == b {
34                     l += 1
35                 }
36                 
37             } else if sum < 0 {
38                 l += 1
39                                 
40                 while l < r && array[l] == b {
41                     l += 1
42                 }
43             } else if sum > 0 {  
44                 r -= 1
45                 
46                 while l < r && array[r] == c {
47                     r -= 1
48                 }
49             }
50         }
51         
52     }
53     
54     func threeSum(_ nums: [Int]) -> [[Int]] {
55         
56         var result = [[Int]]()
57         
58         if nums.count < 3 {
59             return result
60         }
61         
62         let array = nums.sorted {
63             return $0 < $1
64         }
65         
66         for i in 0..<array.count - 2 {
67             if array[i] > 0 {
68                 break
69             }
70             
71             twoSum(array, ignoreIndex: i, result: &result)
72         }
73         
74         return result
75     }
76 }

252ms

 1 class Solution {
 2 func threeSum(_ nums: [Int]) -> [[Int]] {
 3     var MutNums: [Int] = nums
 4     var newNums: [Int] = []
 5     var haha:[[Int]] = []
 6     // 1.排序 对于MutNums[i]来说，我们只需要负数和0，因为三个数之和为0，一定是有一个数为负数的，当然除去三个数都为0的情况。所以，我们取非正数。
 7     MutNums.sort()
 8     for i in 0..<MutNums.count {
 9         if (MutNums[i] > 0) {
10             break;
11         }
12         // 如果两个数字相同，我们直接跳到下一个循环。
13         if (i > 0 && MutNums[i] == MutNums[i-1]) {
14             continue
15         }
16         let target = 0 - MutNums[i];
17         var j = i+1, k = MutNums.count - 1
18         while j < k {
19             // 2.找到后面的两个与MutNums[i]对应的数字
20             if (MutNums[j] + MutNums[k] == target) {
21                 newNums.append(MutNums[i])
22                 newNums.append(MutNums[j])
23                 newNums.append(MutNums[k])
24                 haha.append(newNums)
25                 newNums.removeAll()
26                 // 如果两个数字相同，我们直接跳到下一个循环。
27                 while j < k && MutNums[j] == MutNums[j+1] {
28                     j = j + 1
29                 }
30                 // 如果两个数字相同，我们直接跳到下一个循环。
31                 while j < k && MutNums[k] == MutNums[k-1] {
32                     k = k - 1
33                 }
34                 // 否则就往中间靠拢
35                 j = j + 1;k = k - 1
36             }else if (MutNums[j] + MutNums[k] < target) {
37                 // 如果后面两数相加小于target，说明左边还得往右移
38                 j = j + 1
39             }else {
40                 // 如果后面两数相加大于target，说明右边就要往左移
41                 k = k - 1
42             }
43         }
44     }
45     return haha
46 }
47 }