3sum

名字念起来很羞耻啊... 这道题也没其他的，就是一个对撞指针的加强版，因为三指针的存在，还有题目中要求的不要有重复结果，所以查重已经指针重叠的情况需要异常注意，这段代码已经背下来可以作为三指针，四指针题目的模板使用了（查重是关键！）

class Solution(object):
    def threeSum(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        nums.sort()
        n = len(nums)
        base = 0
        res = []

        while base <= n - 3:
            a = nums[base]
            if base > 0 and nums[base] == nums[base - 1]:
                base += 1
                continue
            st, ed = base + 1, n - 1
            while st <= ed - 1:
                b, c = nums[st], nums[ed]
                if a + b + c == 0:
                    res.append([a, b, c])
                    while ed > st and nums[ed] == nums[ed - 1]:
                        ed -= 1
                    while ed > st and nums[st] == nums[st + 1]:
                        st += 1
                    ed -= 1
                elif a + b + c < 0:
                    st += 1
                else:
                    ed -= 1
            base += 1

        return res

这里要注意，3sum用的三指针是固定指针在左，两个活动指针在固定指针右侧的区域活动，而有些题的三指针是固定指针在右，活动指针在左才能求得正确答案，映象中有一个三角形判断的题目就是这样的