15. 三数之和

给定一个包含 n 个整数的数组nums，判断nums中是否存在三个元素 a，b，c ，使得a + b + c = 0 ？找出所有满足条件且不重复的三元组。

注意：答案中不可以包含重复的三元组。

例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4]，

满足要求的三元组集合为：

[

  [-1, 0, 1],

  [-1, -1, 2]

]

class Solution:

    def threeSum(self, nums):

        """

        :type nums: List[int]

        :rtype: List[List[int]]

        """

        num_dict = self.list2dict(nums)

        num_negative = num_dict['num_negative']

        num_positive = num_dict['num_positive']

        num_results = []

        for i in range(len(num_negative)):

            for j in range(len(num_positive)):

                list_result = []

                list_result.append(num_negative[i])

                list_result.append(num_positive[j])

                sum = num_negative[i] + num_positive[j]

                sum = -sum

                if sum<0:

                    if sum < num_negative[i]:

                        break

                else:

                    if sum < num_positive[j]:

                        continue

                if num_negative[i] == num_positive[j] == 0:

                    if num_dict[num_negative[i]]>=3:

                        list_result.append(0)

                elif sum in num_dict:

                    if sum == num_negative[i] or sum == num_positive[j]:

                        if num_dict[sum]>1:

                            list_result.append(sum)

                        else:

                            continue

                    else:

                        list_result.append(sum)

                if len(list_result) == 3:

                    num_results.append(list_result)

        return num_results

    def list2dict(self, nums):

        '''

        数组转换成字典

        :param nums:

        :return:

        '''

        num_dict = {}

        num_positive = []

        num_negative = []

        for i in range(len(nums)):

            if nums[i] in num_dict:

                num_dict[nums[i]]+=1

            else:

                num_dict[nums[i]]=1

                if nums[i]<=0:

                    num_negative.append(nums[i])

                if nums[i]>=0:

                    num_positive .append(nums[i])

        num_dict['num_positive'] = self.paixu(num_positive)

        num_dict['num_negative'] = self.paixu(num_negative)

        return num_dict

    def paixu(self, nums):

        for i in range(len(nums)):

            for j in range(len(nums)-i-1):

                if nums[j] >nums[j+1]:

                    n = nums[j]

                    nums[j] = nums[j+1]

                    nums[j+1] = n

        y=1

        while y < len(nums): #去重

            if nums[y] == nums[y-1]:

                nums.pop(y)

                continue

            else:

                y+=1

        return nums