Leetcode: 15. 3 Sum
- Primary idea: use the Two Pointers to find the remaining 2 indexes that fulfil the requirement
- Time Complexity: O(n^2)
- Space Complexity: O(n)
func threeSum(_ nums: [Int]) -> [[Int]] {
var nums = nums.sorted()
var result = Set<[Int]>() // (Optional) Use Set to avoid duplicated results
for i in 0..<nums.count {
// Stop processing since the sum will always be positive.
if nums[i] > 0 {
break
}
// Ignore duplication
if i > 0 && nums[i] == nums[i - 1] {
continue
}
// 2 pointers to search for indexes from left and right sides of the sorted array
var left = i + 1
var right = nums.count - 1
while left < right {
let sum = nums[i] + nums[left] + nums[right]
if sum == 0 {
result.insert([nums[i], nums[left], nums[right]])
// Ignore same numbers from the left to avoid duplicated results
while left < right && nums[left] == nums[left + 1] {
left += 1
}
// Ignore same numbers from the right to avoid duplicated results
while left < right && nums[right] == nums[right - 1] {
right -= 1
}
left += 1
right -= 1
} else if sum < 0 {
left += 1
} else {
right -= 1
}
}
}
return Array(result)
}
print(threeSum([0,1,1])) // []
print(threeSum([0,0,0])) // [[0, 0, 0]]
print(threeSum([-1,0,1,2,-1,-4])) // [[-1, -1, 2], [-1, 0, 1]]
print(threeSum([2,0,-2,-5,-5,-3,2,-4])) // [[-4,2,2],[-2,0,2]]