【LeetCode】0015 三数之和

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

代码:

# -*- coding:utf-8 -*-

class Solution(object):
    def threeSum(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        res_temp = []
        for i in range(len(nums)):
            temp_list = [0 for _ in range(len(nums))]
            for j in range(len(temp_list)):
                if i == j:
                    temp_list[j] = float('inf')
                    continue
                # b = -c -a
                temp_list[j] = -nums[i] - nums[j]
            for j in range(len(nums)):
                for k in range(len(temp_list)):
                    if nums[j] == temp_list[k] and j != k and i != k and i != j:
                        temp_res = [nums[i], nums[j], nums[k]]
                        temp_res.sort()
                        res_temp.append(temp_res)
        res = []
        for each in res_temp:
            if each not in res:
                res.append(each)
        return res
if __name__ == '__main__':
    nums = [-1, 0, 1, 2, -1, -4]
    print(Solution().threeSum1(nums))

思路：这道题啊，这道题叫肉蛋葱击（不是）。

上面的代码啊，也是不能AC的，超时，唉，看评论好多都是超时的。

这道题的思路其实也不麻烦，做过0001的基本都会了，无非是设a+b=-c然后计算n个c然后去重即可，那超时咋办嘛，大概只能过200多个用例。

思考：看了大佬的评论，这道题可以用两个指针代替两个for，再加上指针遍历的for，实际上我们省去了一层循环，再配合比较严格的剪枝，时间会被压缩的很小。

思路实际上就是在nums（排序好的）列表中，我们首先选定0位元素为a，然后1位元素为b，-1位元素为c，其中两个左右指针分别指向1和-1，这样两个指针不断向内靠近，以此达到对0元素的三数之和的查找目的。

对于剪枝，如果我们a+b+b就大于0了，那么就没有必要查c了，因此c在b的后面永远比当前b大。同理，当a+c+c小于0也是一样。还有就是排序好的列表0号元素大于0，那么该列表中必然不存在三数之和等于0。

对于去重，我们只需让指针跳过与当前数字相同的索引即可，由于数组已经是排序过的，这个操作无疑也是快速的。

def threeSum1(self, nums):
    """
    :type nums: List[int]
    :rtype: List[List[int]]
    """
    res = []
    nums.sort()
    for i in range(len(nums) - 2):
        if nums[i] > 0:  # 排好序之后，如果nums[i]>0，说明后面的数全部大于0
            break
        if i == 0 or nums[i] > nums[i - 1]:  # 去重
            left, right = i + 1, len(nums) - 1
            # 剪枝，两种边界条件，b值已经足够大，即使是b和b的下一位相加都大于0 和c已经足够小，c和c的前一位相加已经小于0
            if nums[i] + nums[left] + nums[left + 1] > 0 or nums[i] + nums[right - 1] + nums[right] < 0:
                continue
            while left < right:
                ident = nums[i] + nums[left] + nums[right]
                if ident == 0:
                    res.append([nums[i], nums[left], nums[right]])
                    left += 1
                    right -= 1
                    # 去重，将与当前结果一样的数字利用指针直接筛掉
                    while left < right and nums[left] == nums[left - 1]:
                        left += 1
                    while left < right and nums[right] == nums[right + 1]:
                        right -= 1
                elif ident < 0:
                    left += 1
                else:
                    right -= 1
    return res