每日一题20201109（15. 三数之和）

题目链接: 15. 三数之和

image.png

解法

• 暴力法

首先可以确定的是暴力法的时间复杂度是O(N³), 所以基本上不考虑此等解法。

• 排序+双指针

思路是先将数组排序（从小到大），然后固定数组的第一位。

定义2个指针（左右指针）分别指向定位数组的后一位和数组最后一位。

如果3个数字加起来比0小，则左指针右移，循环继续。

如果3个数字加起来比0大，则右指针左移，循环继续。

如果3个数字等于0，说明找到了结果，将3个数字放入结果数组中并把左指针右移，右指针左移。

1. 这里需要注意的是，可能会有重复数据产生，为了不产生重复数据，需要确保左移/右移后的值与之前不一致。

2. 如果从固定的数字大于0了，说明右侧不可能有结果了，因为右侧都是大于0的数字，加起来不会大于0了。

3. 如果固定位置与上一个固定位置的值相同，也会产生重复数据，遇到直接跳过就行。

image.png

最终代码

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        # 先对数组进行排序, 为了方便比较元素
        nums = sorted(nums)
        i = 0  # 数组起点
        result = []    # 结果
        while i < len(nums):
            if nums[i] > 0:
                # 大于0的数字可以直接跳过
                break
            if i > 0 and nums[i] == nums[i-1]:
                # 与上一个固定位重复的数字直接跳过
                i += 1
                continue 
            front, back = i+1, len(nums)-1
            while front < back:
                val = nums[i] + nums[back] + nums[front]
                if val < 0:
                    # 说明需要增大数字, front+1
                    front += 1
                elif val > 0:
                    # 说明需要缩小数字, back-1
                    back -= 1
                else:
                    result.append([nums[i], nums[back], nums[front]])
                    front += 1
                    back -= 1
                    # 保证没有重复数组
                    while front < len(nums) and nums[front] == nums[front-1]:
                        front += 1
                    while back >= 0 and nums[back] == nums[back+1]:
                        back -= 1
            i += 1
        return result