LeetCode-15 - 3Sum

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]
]

Solution1

将问题先转换成2sum，然后进行计算
算法复杂度为O

class Solution(object):
    def threeSum(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        result = []
        for i, v in enumerate(nums):
            temp = self.twoSum(0-v, nums[:i] + nums[i+1:])
            for item in temp:
                item.append(v)
                result.append(sorted(item)) if sorted(item) not in result else None
        return result
            
        
    def twoSum(self, sum, nums):
        aset = set()
        result = []
        for i in nums:
            if (sum - i) in aset:
                result.append([sum - i, i])
            else:
                aset.add(i)
        return result

Solution2

1. 将整个列表排序，这是实现下面算法的精髓
2. 整个列表的遍历可以同时从首尾开始

class Solution(object):
    def threeSum(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        result = []
        nums.sort()
        for i in range(len(nums) - 2):
            if i > 0 and nums[i] == nums[i-1]:
                continue
            l, r = i + 1, len(nums) - 1
            while l < r:
                print nums[i], nums[l], nums[r]
                s = nums[i] + nums[l] + nums[r]
                if s < 0:
                    l += 1
                elif s > 0:
                    r -= 1
                else:
                    result.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
        return result

思考

整个算法的精妙之处还在于去重：

1. 首元素的去重，本次的首元素如果跟上一次的首元素相同，则pass
2. 中间元素的去重，2nd元素如果跟它的下一个元素相同，则pass；3rd元素如果跟它的下一个元素相同则pass