Day Day Code: 3Sum三数之和

#Day Day Code: 3Sum三数之和| 来源: 网络整理| 查看: 265

3Sum 三数之和

题目： Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.

Notice that the solution set must not contain duplicate triplets.

翻译一下：顾名思义三个数相加等于0就返回。注意这里不能输出重复的结果，比如[-1,0,1]和[1，0，-1]是一样的答案

思路：不能重复，怎么解决？* 做之前把数组排序就可以完美解决这个问题* 排序后的数组有序，因此遇到相同的数可以跳过。

捋一遍思路：假设我们有一个排序后的数组【-2，-2，0，0，2，2】，3Sum就是三个数相加。所以 1. 定第一个数用一个for循环，从头遍历。如果遇到相同的数字就跳过，这一点可以用一个if语句来解决：if i>0 and nums[i-1]==a: continue 2. 将接下来的步骤看作2Sum问题依旧用双指针解决，不多赘述。这里注意一个小tips：和小了，左指针右移；和大了，右指针左移这里注意：如果左右指针遇到相同的数，怎么办？解决方法和上面一样：

while left < right and nums[left]==nums[left-1]: left += 1

这里只需固定一侧指针即可达到目的，代码会更简洁。

3. 返回结果

话说完了上代码： class Solution(object): def threeSum(self, nums): """ :type nums: List[int] :rtype: List[List[int]] """ res=[] nums.sort() for i,a in enumerate(nums): if i>0 and nums[i-1]==a: continue left=i+1 right=len(nums)-1 while left 0: right -= 1 else: res.append([a,nums[left],nums[right]]) left += 1 while left < right and nums[left]==nums[left-1]: left += 1 return res

ps：本来是想学一下nsum，后来发现菜鸡的我还没学会走就想飞，看了一天，看不懂，遂弃暗投明。先学走路，over。

【本文地址】

公司简介

联系我们