15.3Sum

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.
已知一个整数数组，返回所有的三维向量，这三维向量元素是数组里面的元素，但是三个元素的的下标互不相等，却元素值之和为零。

Notice that the solution set must not contain duplicate triplets.
答案中不能包含相同的三维向量组合。

说明返回的结果中可能会包含多种答案的二维多行三列的数组。

Constraints：
0 <= nums.length <= 3000
-105 <= nums[i] <= 105
从题目限制里面可以看出，暴力法可行。因为最大长度不是很大，但是也不可取。毕竟暴力法是最坏的方案。

题目思索

暴力法

嵌套循环，遍历不同种的两两组合，然后计算0-两者之和判断这个数值是否存在切下标与其他两个不相等。如果是既保存。
存入之前还需要解决方案是否已经存在答案里面。

暴力法的难点，可能就在于不好判断答案是否已经存在了。依旧使用暴力法：先判断第一个元素是否存在于这一个三元素的答案中，在判断第二个元素。如果两个元素都在答案中， 第三个元素必然处答案中了。这时候还需要注意判断是否存在的情况，还需要区分两个元素相等的情况。
。。。
想了想好想只能想到暴力破解法

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        def is_ex(tri: List[List[int]], nums:List[int]):
            for i in range(len(tri)):
                if tri[i][0] in nums and tri[i][1] in nums and tri[i][2] in nums:
                    if nums[0] in tri[i] and nums[1] in tri[i] and nums[2] in tri[i]:
                        return True
                else:
                    continue
            return False
                
        i_nums = len(nums)-1
        ret = []
        for i in range(i_nums):
            for j in range(i+1, i_nums):
                tmp = 0-nums[i]-nums[j]
                if j>=i_nums or tmp not in nums[j+1:]:
                    continue
                elif not is_ex(ret, [nums[i], nums[j], tmp]):
                    ret.append([nums[i], nums[j], tmp])
                
        return ret

好吧，最后还是超时了。。

答案解析

排序+双指针

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        n = len(nums)
        nums.sort()
        ans = list()
        
        # 枚举 a
        for first in range(n):
            # 需要和上一次枚举的数不相同
            if first > 0 and nums[first] == nums[first - 1]:
                continue
            # c 对应的指针初始指向数组的最右端
            third = n - 1
            target = -nums[first]
            # 枚举 b
            for second in range(first + 1, n):
                # 需要和上一次枚举的数不相同
                if second > first + 1 and nums[second] == nums[second - 1]:
                    continue
                # 需要保证 b 的指针在 c 的指针的左侧
                while second < third and nums[second] + nums[third] > target:
                    third -= 1
                # 如果指针重合，随着 b 后续的增加
                # 就不会有满足 a+b+c=0 并且 b<c 的 c 了，可以退出循环
                if second == third:
                    break
                if nums[second] + nums[third] == target:
                    ans.append([nums[first], nums[second], nums[third]])
        
        return ans

对于去重问题，这边有一个很好的解决方法。将数组进行排序，确保a>=b>=c。
这样就省去了去重的步骤。
里面实现的步骤感觉和我的差不多。就不详细赘述了。

总结

还是思考的太简单了，每次都需要提交很多次，才能得到想要的答案。

哈希表可以进行去重操作。