[数据结构与算法]菜鸟扣代码第55天--Leetcode第15题： 三数之和

题目描述：

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

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

示例 1：

输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
示例 2：

输入：nums = []
输出：[]
示例 3：

输入：nums = [0]
输出：[]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/3sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

代码：

nums = list(map(int,input().split()))
n = len(nums)
nums.sort()
res = []
for k in range(n-2):
    if nums[k] > 0:
        break  
    if k > 0 and nums[k] == nums[k - 1]:
        continue
    i,j = k+1,n-1
    while i < j:
        s = nums[k] + nums[i] + nums[j]
        if s == 0:
            res.append([nums[k],nums[i],nums[j]])
            i += 1
            j -= 1
        elif s > 0:
            j -= 1
            while nums[j] == nums[j-1]:
                j -= 1
        else:
            i += 1
            while nums[i] == nums[i+1]:
                i += 1
print(res)

思路：

这个题目写出一个超时的方法并不难，但是为了解决超时的问题，着实费了一番功夫。我的解决方案是先将列表排序，之后利用固定第一个数（k）进行循环，之后采用双指针的思想，记录第二个数（i=k+1）和第三个数（j=n-1），记录三个数的和s，如果s>0则j-1；如果s<0则i+1，前提条件是i<j。