[Array] add Solution to 3Sum

Yi Gu · Yi Gu · commit 21886bdf90ff · 2016-04-24T01:01:59.000-07:00
diff --git a/Array/ThreeSum.swift b/Array/ThreeSum.swift
@@ -0,0 +1,51 @@
+/**
+ * Question Link: https://leetcode.com/problems/3sum/
+ * Primary idea: Sort the array, and traverse it, increment left or decrease right 
+ *               predicated on their sum is greater or not than the target
+ * Time Complexity: O(n^2), Space Complexity: O(n)
+ */
+
+class ThreeSum {
+    func threeSum(nums: [Int]) -> [[Int]] {
+        var nums = nums.sort({$0 < $1})
+        var res = [[Int]]()
+        
+        if nums.count <= 2 {
+            return res
+        }
+        
+        for i in 0...nums.count - 3 {
+            if i == 0 || nums[i] != nums[i - 1] {
+                var remain = -nums[i]
+                var left = i + 1
+                var right = nums.count - 1
+                while left < right {
+                    if nums[left] + nums[right] == remain {
+                        var temp = [Int]()
+                        temp.append(nums[i])
+                        temp.append(nums[left])
+                        temp.append(nums[right])
+                        
+                        res.append(temp)
+                        repeat {
+                            left += 1
+                        } while (left < right && nums[left] == nums[left - 1])
+                        repeat {
+                            right -= 1
+                        } while (left < right && nums[right] == nums[right + 1])
+                    } else if nums[left] + nums[right] < remain {
+                        repeat {
+                            left += 1
+                        } while (left < right && nums[left] == nums[left - 1])
+                    } else {
+                        repeat {
+                            right -= 1
+                        } while (left < right && nums[right] == nums[right + 1])
+                    }
+                }
+            }
+        }
+        
+        return res
+    }
+}
