一、题目

3Sum

二、解题

使用三重循环遍历进行判断，得出的结果使用sort进行排序，判断是否在列表之内再添加。

三、尝试与结果

1）首次尝试

class Solution(object):
    def threeSum(self, nums):
        length = len(nums)
        resultList = []
        for i in range(0,length):
            for j in range(i+1,length):
                for k in range(j+1,length):
                    tSum = nums[i] + nums[j] + nums[k]
                    if tSum == 0:
                        result = []
                        result.append(nums[i])
                        result.append(nums[j])
                        result.append(nums[k])
                        result.sort()
                        if result not in resultList:
                            resultList.append(result)
        return resultList

结果：TL

2）再次尝试，先进行sort排序，在三重循环中加入break判断，当大于0时就跳出。

class Solution(object):
    def threeSum(self, nums):
        length = len(nums)
        resultList = []
        nums.sort()
        for i in range(0,length-2):
            if nums[i] > 0: 
                break
            for j in range(i+1,length-1):
                if nums[i] + nums[j] > 0:
                    break
                for k in range(j+1,length):
                    if nums[i] + nums[j] + nums[k] == 0:
                        result = []
                        result.append(nums[i])
                        result.append(nums[j])
                        result.append(nums[k])
                        if result not in resultList:
                            resultList.append(result)
                    if nums[i] + nums[j] + nums[k] > 0:
                        break
        return resultList

结果：TL

3）O（n3）的时间复杂度经过修改也没啥用，改成：

• 固定i，j、k为双向指针，j从头开始，k从尾开始遍历。
• 当和小于0时，j减1，当和大于0时，k加1
• 当找到一个值时，不能当做此时i的固定结果，因为可能有多个，所以需要再把j、k其中之一改变，j加1或者k减1都可以

class Solution(object):
    def threeSum(self, nums):
        length = len(nums)
        resultList = []
        nums.sort()
        for i in range(0,length-2):
            j = i + 1
            k = length - 1
            while (j < k):
                sum0 = nums[i] + nums[j] + nums[k]
                if (sum0 == 0):
                    result = []
                    result.append(nums[i])
                    result.append(nums[j])
                    result.append(nums[k])
                    if result not in resultList:
                        resultList.append(result)
                    j +=1
                if (sum0 < 0):
                    j +=1
                if (sum0 > 0):
                    k -=1
        return resultList

结果：AC