O(N^2)的解法, 对sum排序。先定下来a,在从a~末尾的这一段区间里找b,c, 两头往中间走。需要注意去重, 对于num=[-4,-1,-1,0,1,2]不要出来两组(-1,0,1)

class Solution:
    # @return a list of lists of length 3, [[val1,val2,val3]]
    def threeSum(self, num):
        res = []
        sortnum = sorted(num)
        length = len(sortnum)
        # make sure a < b < c
        for i in xrange(length-2):
            a = sortnum[i]
            # remove duplicate a
            if i >= 1 and a == sortnum[i-1]:
                continue
            j = i + 1
            k = length - 1
            while j < k:
                b = sortnum[j]
                c = sortnum[k]
                if b + c == -a:
                    res.append([a,b,c])
                    # remove duplicate b,c
                    while j < k:
                        j += 1
                        k -= 1
                        if sortnum[j] != b or sortnum[k] != c:
                            break
                elif b + c > -a:
                    # remove duplicate c
                    while j < k:
                        k -= 1
                        if sortnum[k] != c:
                            break
                else:
                    # remove duplicate b
                    while j < k:
                        j += 1
                        if sortnum[j] != b:
                            break
        return res