| 11 | |
| 12 | class Solution(object): |
| 13 | def threeSum(self, nums): |
| 14 | if nums == None or len(nums) < 3: |
| 15 | return [] |
| 16 | elif len(nums) == 3 and sum(nums) == 0: |
| 17 | return [sorted(nums)] |
| 18 | |
| 19 | nums.sort() # sorted, O(nlogn) |
| 20 | result, length = [], len(nums) |
| 21 | for i in range(length - 2): |
| 22 | if i > 0 and nums[i-1] == nums[i]: |
| 23 | continue |
| 24 | l, r = i + 1, length - 1 # i < l < r |
| 25 | while l < r: |
| 26 | Sum = nums[i] + nums[l] + nums[r] |
| 27 | if Sum == 0: |
| 28 | result.append([nums[i], nums[l], nums[r]]) |
| 29 | while l < r and nums[l] == nums[l + 1]: # if appear same integer, l move right 1 place |
| 30 | l += 1 |
| 31 | while l < r and nums[r] == nums[r - 1]: # if appear same integer, r move left 1 place |
| 32 | r -= 1 |
| 33 | if Sum > 0: |
| 34 | r -= 1 |
| 35 | else: |
| 36 | l += 1 |
| 37 | return result |
| 38 | s = Solution() |
| 39 | print(s.threeSum([0, 0, 0, 0, 0])) |