LeetCode-15. 3Sum

[ninehills]

问题

Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note: The solution set must not contain duplicate triplets.

For example, given array S = [-1, 0, 1, 2, -1, -4],

A solution set is:
[
  [-1, 0, 1],
  [-1, -1, 2]
]

思路

• 最基本的思路是将array求出全部子集，然后找匹配的结果并消重。用Python很容易计算而出，但是这种方法很明显会超出时间限制
• O(n^2)方法1: sort array，然后对每个元素，找匹配的三个元素，因为排序，所以相当于只有两次遍历
• O(n^2)方法2: 前两个元素两次循环，使用hash表，看第三个元素是否在hash表中（hash表中的元素为 0 - a-b）

参考： https://en.wikipedia.org/wiki/3SUM

解答

#coding=utf8
class Solution(object):
    def threeSumHash(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        d = {j: i for i,j in enumerate(nums)}
        ret = set()
        for i,j in enumerate(nums):
            for k,v in enumerate(nums[i+1:]):
                x = 0-j-v
                #print i,j,k,v
                if x in d and d[x] != i and d[x] != i+k+1:
                    ret.add(tuple(sorted([j, v, 0-j-v])))
        return list(ret)

    def threeSum(self, nums):
        """Sort"""
        nums.sort()
        ret = set()
        for i in range(len(nums) - 2):
            if i > 0 and nums[i-1] == nums[i]:
                # 如果和前一位相等，直接忽略，避免重复结果
                continue
            l = i + 1
            r = len(nums) - 1
            while l < r:
                s = nums[l] + nums[r] + nums[i]
                if s == 0:
                    ret.add((nums[i], nums[l], nums[r]))
                    l = l + 1
                    r = r - 1
                elif s > 0:
                    r = r - 1
                else:
                    l = l + 1
        return list(ret)

print Solution().threeSum([0,0])
print Solution().threeSum([-1,0,1,2,-1,-4])
print Solution().threeSum([-2,0,0,2,2])

[ninehills]

20170724