leetcode(8)-三数之和

给定一个包含 n 个整数的数组?nums，判断?nums?中是否存在三个元素 a，b，c ，使得?a + b + c = 0 ？找出所有满足条件且不重复的三元组。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/3sum

解题思路

双指针

from collections import defaultdict
class Solution:
    

    def threeSum(self, nums):
        nums = sorted(nums)
        ans = []
        if len(nums)<3:
            return []
        for i in range(len(nums)):
            if i>0 and nums[i-1] == nums[i]:
                continue
            if nums[i]>0:
                break
            L = i+1
            R = len(nums)-1
            while L<R:
                if nums[i]+nums[L]+nums[R]==0:
                    ans.append([nums[i],nums[L],nums[R]])
                    while L<R and nums[L]==nums[L+1]:
                        L+=1
                    while L<R and nums[R] ==nums[R-1]:
                        R-=1
                    L+=1
                    R-=1
                elif nums[i]+nums[L]+nums[R]>0:
                    R-=1
                elif nums[i]+nums[L]+nums[R]<0:
                    L+=1
        return ans
#s = Solution()
#print(s.threeSum([0,0,0]))

利用数学性质

class Solution:
    def threeSum(self, nums):
        hashmap = {}
        res = []
        for i, x in enumerate(nums):
            hashmap[x] = hashmap.get(x, 0) + 1                 #get(x,0)的含义：如果无x，加入x并记录次数1；如果有x，x出现次数加一
        
        if 0 in hashmap and hashmap[0] >= 3:
            res.append([0, 0, 0])
        
        neg = list(filter(lambda x: x < 0, hashmap))
        pos = list(filter(lambda x: x >= 0, hashmap))
        
        for i in neg:
            for j in pos:
                k = 0 - i - j
                if k in hashmap:
                    if (k == i or k == j) and hashmap[k] >= 2:
                        res.append([i, j, k])
                    if k < i or k > j: # 避免重复，要求i,j是连续的
                        res.append([i, j, k])
        return res
s = Solution()
print(s.threeSum([0,0,0]))

leetcode(8)-三数之和

原文：https://www.cnblogs.com/Lzqayx/p/12141624.html