lc15. 三数之和

题目链接：15. 三数之和 - 力扣（Leetcode）

题解

写了挺久的，不是标解。假设 $a+b+c=0, a \le b \le c$，枚举 ab，然后去一个 map 里面找有没有 c。另外还要记录一下 ab 有没有重复过。

标解里面，先对数组排序，然后 c 用双指针的思路在数组里查找。

参考代码

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        ret = []
        used = {}
        tmp = {}
        n = len(nums)
        for i in range(n):
            if nums[i] not in tmp:
                tmp[nums[i]] = []
            tmp[nums[i]].append(i)

        for i in range(n):
            for j in range(i+1, n):
                key = (str(nums[i]) + "_" + str(nums[j]))
                if key in used:
                    continue
                used[key] = 1
                need = 0 - (nums[i] + nums[j])
                if need < nums[j]:
                    continue
                if need not in tmp:
                    continue
                for k in tmp[need]:
                    if k == i or k == j:
                        continue
                    ret.append((nums[i], nums[j], nums[k]))
                    break
        
        return ret

超时

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        two_sum = defaultdict(list)
        n = len(nums)

        for i in range(n):
            for j in range(i+1, n):
                s = nums[i] + nums[j]
                two_sum[s].append((i, j))

        ret = []
        used = {}
        for i in range(n):
            need = 0 - nums[i]
            for (a, b) in two_sum[need]:
                if a == i or b == i:
                    continue
                tmp = [nums[i], nums[a], nums[b]]
                tmp.sort()
                key = "_".join(map(str, tmp))
                if  key in used:
                    continue
                used[key] = 1
                ret.append((nums[i], nums[a], nums[b]))
        
        return ret