Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.
Note:
- Elements in a triplet (a,b,c) must be in non-descending order. (ie, a ≤ b ≤ c)
- The solution set must not contain duplicate triplets.
For example, given array S = {-1 0 1 2 -1 -4}, A solution set is: (-1, 0, 1) (-1, -1, 2)
AC代码:
class Solution(object): def threeSum(self, nums): ret_list = [] nums.sort() for i, vi in enumerate(nums[:-2]): if i - 1 >= 0 and vi == nums[i - 1]: continue temp_list = [] j = i + 1 while j < len(nums): need_val = - vi - nums[j]; if need_val in temp_list: ret_list.append([vi, need_val, nums[j]]) temp_list.remove(need_val) elif nums[j] not in nums[i+1: j]: temp_list.append(nums[j]) j += 1 return ret_list
此方法较为非主流,核心思想是用一个临时列表用来存放遍历过不符合要求的值,每次取新值来运算,如果和等于0则这一条加入返回列表。为了防止重复还需要在临时列表中删除已经合法的值。效率一般。
较为主流的解法是用两个指针:
class Solution(object): def threeSum(self, nums): ret_list = [] nums.sort() for i_1st in xrange(len(nums) - 2): if nums[i_1st] > 0: break # remove duplicates if i_1st > 0 and nums[i_1st] == nums[i_1st - 1]: continue i_2nd, i_3rd = i_1st + 1, len(nums) - 1 while i_2nd < i_3rd: s = nums[i_1st] + nums[i_2nd] + nums[i_3rd] if s > 0: i_3rd -= 1 elif s < 0: i_2nd += 1 else: ret_list.append([nums[i_1st], nums[i_2nd], nums[i_3rd]]) # remove duplicates while i_2nd < i_3rd and nums[i_2nd] == nums[i_2nd + 1]: i_2nd += 1 while i_2nd < i_3rd and nums[i_3rd] == nums[i_3rd - 1]: i_3rd -= 1 i_2nd += 1; i_3rd -= 1 return ret_list
因为首先进行了排序,所以用两个指针分别从首尾两端进行缩小,效率更高。注意处理重复的情况。
上面两种方法都需要先进行排序。