原题给定一个包含 n 个整数的数组 nums判断 nums 中是否存在三个元素 abc 使得 a b c 0 找出所有满足条件且不重复的三元组。注意答案中不可以包含重复的三元组。例如, 给定数组 nums [-1, 0, 1, 2, -1, -4]满足要求的三元组集合为[[-1, 0, 1],[-1, -1, 2]]解法一主要思路是通过先确定最左边的元素之后就成为了tow Sum的问题了关于Tow Sum我们可以使用双指法去确定元素的位置注意我们这里需要避免重复的元素所以当碰到重复的元素我们直接跳过就可以了.第二因为这里是数组问题我之前说过关于数组问题我可以优先考虑先进行排序预处理再解决题目。classSolution(object):defthreeSum(self,nums): :type nums: List[int] :rtype: List[List[int]] nums.sort()# 进行排序res,k[],0forkinrange(len(nums)-2):# 开始确定第一个元素位置ifnums[k]0:break# 1. because of j i k.ifk0andnums[k]nums[k-1]:continue# 2. skip the same nums[k].i,jk1,len(nums)-1whileij:# 3. double pointersnums[k]nums[i]nums[j]ifs0:i1whileijandnums[i]nums[i-1]:i1# 跳过相同的elifs0:j-1whileijandnums[j]nums[j1]:j-1# 跳过相同的else:res.append([nums[k],nums[i],nums[j]])i1j-1whileijandnums[i]nums[i-1]:i1# 跳过相同的whileijandnums[j]nums[j1]:j-1# 跳过相同的returnres解法二将数组分为三块。第一块全为负数第二块全是0第三块全为正数。我尝试将中间一块取最小的非负数的但是程序实现很复杂。classSolution(object):deffunction(self,left,right):ret[]iflen(left)1andlen(right)0:foriinrange(len(left)-1):forjinrange(i1,len(left)):temp-1*(left[i]left[j])iftempinright:min_valmin(left[i],temp,left[j])max_valmax(left[i],temp,left[j])ret.append([min_val,0-min_val-max_val,max_val])returnretdefthreeSum(self,nums): :type nums: List[int] :rtype: List[List[int]] nums.sort()ret[]left[]right[]mid[]foriinrange(len(nums)):ifnums[i]0:left.append(nums[i])elifnums[i]0:right.append(nums[i])else:mid.append(nums[i])iflen(left)0andlen(mid)andlen(right)0:# 左右两边各自取一个iflen(left)len(right):templeftelse:temprightforiinrange(len(temp)):ifi1len(temp)andtemp[i]temp[i1]:continueif-1*temp[i]innums:ret.append([min(temp[i],-temp[i]),0,max(temp[i],-temp[i])])retretself.function(left,right)self.function(right,left)iflen(mid)2:ret.append([0,0,0])result[]foriteminret:ifitemnotinresult:result.append(item)returnresult最后超出时间限制了。
LSGO——LeetCode实战（数组系列）: 15题 三数之和 (three Sum)
原题给定一个包含 n 个整数的数组 nums判断 nums 中是否存在三个元素 abc 使得 a b c 0 找出所有满足条件且不重复的三元组。注意答案中不可以包含重复的三元组。例如, 给定数组 nums [-1, 0, 1, 2, -1, -4]满足要求的三元组集合为[[-1, 0, 1],[-1, -1, 2]]解法一主要思路是通过先确定最左边的元素之后就成为了tow Sum的问题了关于Tow Sum我们可以使用双指法去确定元素的位置注意我们这里需要避免重复的元素所以当碰到重复的元素我们直接跳过就可以了.第二因为这里是数组问题我之前说过关于数组问题我可以优先考虑先进行排序预处理再解决题目。classSolution(object):defthreeSum(self,nums): :type nums: List[int] :rtype: List[List[int]] nums.sort()# 进行排序res,k[],0forkinrange(len(nums)-2):# 开始确定第一个元素位置ifnums[k]0:break# 1. because of j i k.ifk0andnums[k]nums[k-1]:continue# 2. skip the same nums[k].i,jk1,len(nums)-1whileij:# 3. double pointersnums[k]nums[i]nums[j]ifs0:i1whileijandnums[i]nums[i-1]:i1# 跳过相同的elifs0:j-1whileijandnums[j]nums[j1]:j-1# 跳过相同的else:res.append([nums[k],nums[i],nums[j]])i1j-1whileijandnums[i]nums[i-1]:i1# 跳过相同的whileijandnums[j]nums[j1]:j-1# 跳过相同的returnres解法二将数组分为三块。第一块全为负数第二块全是0第三块全为正数。我尝试将中间一块取最小的非负数的但是程序实现很复杂。classSolution(object):deffunction(self,left,right):ret[]iflen(left)1andlen(right)0:foriinrange(len(left)-1):forjinrange(i1,len(left)):temp-1*(left[i]left[j])iftempinright:min_valmin(left[i],temp,left[j])max_valmax(left[i],temp,left[j])ret.append([min_val,0-min_val-max_val,max_val])returnretdefthreeSum(self,nums): :type nums: List[int] :rtype: List[List[int]] nums.sort()ret[]left[]right[]mid[]foriinrange(len(nums)):ifnums[i]0:left.append(nums[i])elifnums[i]0:right.append(nums[i])else:mid.append(nums[i])iflen(left)0andlen(mid)andlen(right)0:# 左右两边各自取一个iflen(left)len(right):templeftelse:temprightforiinrange(len(temp)):ifi1len(temp)andtemp[i]temp[i1]:continueif-1*temp[i]innums:ret.append([min(temp[i],-temp[i]),0,max(temp[i],-temp[i])])retretself.function(left,right)self.function(right,left)iflen(mid)2:ret.append([0,0,0])result[]foriteminret:ifitemnotinresult:result.append(item)returnresult最后超出时间限制了。
