15. 3Sum

题目

Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note: The solution set must not contain duplicate triplets.

1
2
3
4
5
6
7
For example, given array S = [-1, 0, 1, 2, -1, -4],

A solution set is:
[
[-1, 0, 1],
[-1, -1, 2]
]

题目大意

对于一个整型数组,找出所有不同组合的三个元素,能使三个元素相加之和为0,

解题思路

  • 对数组进行排序
  • 逐一遍历数组,对于相同的元素,只处理一次,其余跳过
  • 对于每个元素nums[i],其余两个值在[i+1,len(nums)-1]范围内查找
  • 在查找其余两个值的时候,跳过重复的值

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution(object):
def threeSum(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
result = []
nums.sort()
'''
忽略中间的相同的数值,比如[1,1,1,1,1,3],则只计算第一个1,其余忽略
对于每个数nums[i],其余两个值在[i+1,len(nums)-1]范围内查找
'''
for i in range(len(nums)-1):
if i>0 and nums[i] == nums[i-1]:
continue
l,r = i+1,len(nums)-1
while l<r:
tsum = nums[i] + nums[l] + nums[r]
if tsum > 0:
r -= 1
elif tsum < 0:
l += 1
else:
result.append([nums[i],nums[l],nums[r]])
"""
可能还有其他的可能性,跳过l,r中相同的元素
"""
while l < r:
if nums[l] == nums[l+1]:
l += 1
elif nums[r] == nums[r-1]:
r -= 1
else:
break
l += 1
r -= 1
return result

本文标题:15. 3Sum

文章作者:定。

发布时间:2017年7月11日 - 16时07分

本文字数:1,200字

原始链接:http://cocofe.cn/2017/07/11/3Sum/

许可协议: Attribution-NonCommercial 4.0

转载请保留以上信息。