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 1:

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

Related Topics: ArrayTwo Pointers

解題邏輯與實作

1. 是答案會出現同結果
2. 是很容易 Time Limit Exceeded。

 1234567891011121314151617181920212223242526272829303132333435363738394041424344 class Solution: def threeSum(self, nums: List[int]) -> List[List[int]]: nums.sort() if not nums or (nums[0] > 0 or nums[-1] < 0) : return [] length = len(nums) answers = [] for first_idx, first in enumerate(nums[:-2]): if first > 0 : break if first_idx > 0 and first == nums[first_idx-1]: continue diff = 0 - first second_idx = first_idx + 1 third_idx = length -1 while(second_idx < third_idx): second = nums[second_idx] third = nums[third_idx] summation = second + third if summation < diff: second_idx += 1 elif summation > diff: third_idx -= 1 else: answers.append([first,second,third]) while(second_idx < third_idx and nums[second_idx] == nums[second_idx+1]): second_idx += 1 while(second_idx < third_idx and nums[third_idx] == nums[third_idx-1]): third_idx -= 1 second_idx += 1 third_idx -= 1 return answers