15.三数之和

看题目中0 <= nums.length <= 3000就知道答案应该是O(n^2)及以下的算法。 根据之前做的两数之和一样的思路，用dict保存元素，实现n^2的算法

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        indexs = {}
        for i, num in enumerate(nums):
            index = indexs.get(num, [])
            index.append(i)
            indexs[num] = index
        res = set()
        for i in range(len(nums)-2):
            for j in range(i+1, len(nums)-1):
                for k in indexs.get(- nums[i] - nums[j], []):
                    if k not in [i,j]:
                        s = tuple(sorted([nums[i], nums[j], - nums[i] - nums[j]]))
                        res.add(s)
                        break
        return list(res)

通过了，但是成绩比较差，只击败了5%左右的人。看了下题解，可以用双指针，但是双指针写下来其实也是O(n^2)的

评论