---
title: "#15 3Sum"
tags: LeetCode, Top100
---
#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.

Notice that the solution set must not contain duplicate triplets.

Example 1:
--
>Input: nums = [-1,0,1,2,-1,-4]
>Output: [[-1,-1,2],[-1,0,1]]

解題思維
--
利用差值找出另外兩個不重複的解。

BruteForce
--

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums = sorted(nums)
        result = set()
        for i in range(len(nums)-2):
            l = i + 1
            r = len(nums) - 1
            target = 0 - nums[i]
            while l < r:
                if nums[l] + nums[r] == target:
                    result.add((nums[i], nums[l], nums[r]))
                    l += 1
                    r -= 1
                elif nums[l] + nums[r] < target:
                    l += 1
                else:
                    r -= 1
        return list(result)