3 双指针问题 leetcode15 三数之和

题目描述

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

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

示例 1:

给定数组 nums = [-1, 0, 1, 2, -1, -4]，

满足要求的三元组集合为：
[
  [-1, 0, 1],
  [-1, -1, 2]
]

官方难度

Medium

解决思路

最简单粗暴的解决思路，三层循环，

优化

两层循环，利用字典存储相加以后剩下的数字，如果第二层遍历有符合条件的值，则添加进去：

根据上面的分析，我们可以很容易的得到直接方案的流程如下：

1. 遍历nums, 构建记忆字典memo.
2. 从i+1开始遍历数组nums,
3. memo[0-nums[i+1]- nums[j]] = [(i+1, j)]
4. 如果nums[j]在memo中则加入到结果中。

基于这个流程，我们可以实现类似下面的代码：

class Solution(object):
    def threeSum(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        res = []
        for i in range(len(nums)):
            memo = {}
            for j in range(i + 1, len(nums)):
                if nums[j] in memo:
                    for each in memo[nums[j]]:
                        each.append(nums[j])
                        temp = sorted(each)
                        if temp not in res:
                            res.append(temp)
                    del memo[nums[j]]
                sub_val = 0 - nums[i] - nums[j]
                if sub_val not in memo:
                    memo[sub_val] = []
                memo[sub_val].append([nums[i], nums[j]])
        return res

继续优化

上面的解法仍然是O(n^2)的复杂度，我们可以先排序，然后使用左右双指针再遍历一遍，复杂度更小。双指针思路如下：

1. 遍历数组 ，求 0-nums[i],下面问题就变成了左右指针求和为-nums[i]的问题
2. 设定start ,end为左右指针
3. 如果nums[start]+nums[end] > -nums[i], 将end--
4. 如果 nums[start]+nums[end] < -nums[i] , 将start++
5. 结束条件start == end;
6. 去除重复数组的条件，1）排序后，相同的数字可以跳过。2）计算过程中，如果有符合条件的start和end，start和end相同的可以跳过。加入此条件可以通过leetcode的检查

基于这个流程，我们可以实现类似下面的代码：

class Solution(object):
    def threeSum(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        res = []
        nums = sorted(nums)
        for i in range(len(nums)):
            start = i + 1
            end = len(nums) -1
            sub_val = 0 - nums[i]
            if nums[i] == nums[i-1] and i > 0:
                continue
            while start < end:
                if sub_val == nums[start] + nums[end]:
                    res.append([nums[i], nums[start], nums[end]])
                    while(start < end and nums[start] == nums[start+1]):
                        start += 1
                    while(start < end and nums[end] == nums[end-1]):
                        end -= 1
                    start += 1
                    end -= 1
                elif sub_val > nums[start] + nums[end]:
                    start += 1
                else:
                    end -= 1
        return res

总结

这题为Medium难度，大部分人都能想到暴力破解，但是如果能在面试过程中，不断优化，面试过程中是可以加分的。