15. 3Sum.md

15. 3Sum

Given an array nums of n integers, are there elements a, b, c in nums 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.

Example:

Given array nums = [-1, 0, 1, 2, -1, -4],

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

Given an array nums of n integers, are there elements a, b, c in nums 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.

Example:

Given array nums = [-1, 0, 1, 2, -1, -4],

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

Solution:

两年前用c++写过，完全忘了，当时大概也是看了答案的。

现在还是看了答案的。

毫无长进。

SolutionV2

忘了AddSum2吧！！这个方法能给你快乐！！

要记得务必记得如何去掉重复！！有好几处都要注意的！

Code:

class Solution:
    def threeSum(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        res = []
        if len(nums) <= 2:
            return res

        nums.sort()
        for i in range(len(nums)-2):
            if i != 0 and nums[i] == nums[i-1]:
                continue
            l = i + 1
            r = len(nums)-1
            while l < r:
                cur = nums[l] + nums[r] + nums[i]
                if cur < 0:
                    l += 1
                elif cur > 0:
                    r -= 1
                else:
                    res.append([nums[l], nums[r], nums[i]])
                    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 res

CodeV2(with TwoSum)

class Solution(object):
    def twoSum(self, nums, st, target):
        numap = {}
        res = []
        for i in range(st,len(nums)):
            num = nums[i]
            if i < len(nums)-1 and num==nums[i+1]:
                numap[target-num] = 1
                continue
            if numap.has_key(num):
                res.append([target-num, num])
                continue
            numap[target-num] = 1
        return res
            
            
    def threeSum(self, nums):
        res = []
        nums.sort()
        print(nums)
        for i, x in enumerate(nums):
            if i > 0 and x == nums[i-1]:
                continue
            cur_list = self.twoSum(nums, i+1, -nums[i])
            # print(i)
            # print(cur_list)
            # print('---')
            for lis in cur_list:
                lis.append(x)
                res.append(lis)
        return res