--

leetcode 015: 3 sum

https://leetcode.com/problems/3sum/

---

---

problem:

---

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

---

---

start code (c++)

---

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        

---

---

solution:

我的思路：
解题思路是和 2 sum 很类似的，但是难点在于如何避免重复？ 1. 排序 2. 先从左到右确定第一个数，然后再去解决一个 2 sum 问题 但是如果对于 [-1,0,1,2,-1,-4] 的输入，我们很有可能得到了 [[-1,-1,2],[-1,0,1],[-1,0,1]] 中间包含了重复的元素。 当然我们可以在最后做一个判断是不是有重复，但是我们也可以在一开始解的时候避免考虑重复的问题。

---

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums = sorted(nums)
        print(nums)
        solutions = []
        for i, v in enumerate(nums):
            if i > 0 and nums[i] == nums[i -1]:
                continue
            if i > len(nums)-3:
                break
            beg = i + 1
            end = len(nums) - 1
            while end > beg:
                sum3 = v + nums[beg] + nums[end]
                if sum3 > 0:
                    end -= 1
                elif sum3 < 0:
                    beg += 1
                else:
                    solutions.append([v, nums[beg], nums[end]])
                    while (beg < end and nums[beg] == nums[beg +1]):
                        beg += 1
                    beg += 1
                    while (beg < end and nums[end] == nums[end -1]):
                        end -= 1
                    end -= 1
        return solutions

---