LeetCode15-三数之和

题目描述给定一个包含 n 个整数的数组 nums判断 nums 中是否存在三个元素 abc 使得 a b c 0 找出所有满足条件且不重复的三元组。注意答案中不可以包含重复的三元组。例如, 给定数组 nums [-1, 0, 1, 2, -1, -4]满足要求的三元组集合为[[-1, 0, 1],[-1, -1, 2]]来源力扣LeetCode链接https://leetcode-cn.com/problems/3sum著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。首先使用了暴力查找法找出所有的三数组合判断它们之和是否为0但结果会超出时间限制。class Solution: def threeSum(self, nums: List[int]) - List[List[int]]: lengthlen(nums) l1[] for i in range(length-2): for j in range (i1,length-1): for k in range(j1,length): if nums[i]nums[j]nums[k]0: l1.append([nums[i],nums[j],nums[k]]) temp_list[] for one in l1: onesorted(one) if one not in temp_list: temp_list.append(one) return temp_list后来我将nums中的正数和负数分开将0归于正数中然后三个数可能有两种情况2正1负、1正2负分别判断三数之和是否为0还有一种特殊情况nums中有超过3个0如果出现这种情况就将[0,0,0]加进去。但结果仍然超出时间限制。class Solution: def threeSum(self, nums: List[int]) - List[List[int]]: l1,l2,l[],[],[] f0 for num in nums: if num0: l1.append(num) else: l2.append(num) l11len(l1) l22len(l2) for m in l1: if m0: ff1 if f3: l.append([0,0,0]) for i in range(l11): for j in range(l22-1): for k in range(j1,l22): if l1[i]l2[j]l2[k]0: l.append([l1[i],l2[j],l2[k]]) for i in range(l22): for j in range(l11-1): for k in range(j1,l11): if l2[i]l1[j]l1[k]0: l.append([l2[i],l1[j],l1[k]]) temp_list[] for one in l: onesorted(one) if one not in temp_list: temp_list.append(one) return temp_list最后借鉴了别人的做法采用排序双指针的方法,这种方法可排除许多无效解从而降低时间复杂度。class Solution: def threeSum(self, nums:List[int]) - List[List[int]]: nums.sort() l, k [], 0 for k in range(len(nums) - 2): if nums[k] 0: break if k 0 and nums[k] nums[k - 1]: continue i, j k 1, len(nums) - 1 while i j: s nums[k] nums[i] nums[j] if s 0: i 1 while i j and nums[i] nums[i - 1]: i 1 elif s 0: j - 1 while i j and nums[j] nums[j 1]: j - 1 else: l.append([nums[k], nums[i], nums[j]]) i 1 j - 1 while i j and nums[i] nums[i - 1]: i 1 while i j and nums[j] nums[j 1]: j - 1 return l