三数之和

Leetcode Link: 15. 三数之和 - 力扣（LeetCode） (leetcode-cn.com)

题目

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。

注意：答案中不可以包含重复的三元组。

解法一

思路：三重for循环，无敌暴力

解法二

思路：排序 + 对向双指针

题解：

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        if len(nums) < 3:
            return []
        nums.sort()
        res = []
        for head_idx in range(len(nums)-2):
            head = nums[head_idx]
            # 由于已经排好序了，后面不用看
            if head > 0:
                break
 
            left = head_idx+1
            right = len(nums)-1
            while(left != right):
                # 这里一定要用if 和 elif, 不能用三个if，否则会卡住
                if head + nums[left] + nums[right] == 0:
	                # 先查重，用set()不能这样查重
                    if [head, nums[left], nums[right]] not in res:
                        res.append([head, nums[left], nums[right]])
                    left += 1 # 注意这个不能放到这个if的里面，不然会卡住
                    # 只能走一个指针，哪个都行，不能两个都走。
                elif head + nums[left] + nums[right] > 0:
                    right -= 1
                elif head + nums[left] + nums[right] < 0:
                    left += 1
        return res

启发和联系