【leetcode刷题】T2-3Sum
昨天分享了2sum，今天分享leetcode第2篇文章，第15题—3sum，地址是：https://leetcode.com/problems/3sum/
【英文题目】
Given an array nums of n integers, are there elements a, b, c in nums 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.
Example:
Given array nums = [-1, 0, 1, 2, -1, -4],
A solution set is:
[
[-1, 0, 1],
[-1, -1, 2]
]【中文题目】
给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。
注意：答案中不可以包含重复的三元组。
例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4]，
满足要求的三元组集合为：
[
[-1, 0, 1],
[-1, -1, 2]
]【思路】
和2sum比较类似，容易想到两种方法（同2sum）：一是暴力破解，三层for循环；二是使用字典，判断c = -(a+b)是否在字典中并且字典中c的value大于b的下标。但是，两种方法的时间复杂度很高，分别为O(n^3)和O(n^2)，并且还有判断满足条件的组合是否已经存在，造成时间复杂度更高，不能通过测试
暴力破解核心代码
class Solution(object):
def threeSum(self, nums):
length = len(nums)
res = []
if length < 3:
return res
for i in range(length-2):
for j in range(i+1, length-1):
for k in range(j+1, length):
if nums[i] + nums[j] + nums[k] == 0:
# 这里还需要判断该种组合是否存在于res中
res.append([nums[i], nums[j], nums[k]])
return res使用字典
class Solution(object):
def threeSum(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
length = len(nums)
# 字典，value为最后一个相同元素的下标
d = {}
for i in range(length):
d[nums[i]] = i
res = []
# 数组元素个数必须要大于3
if length < 3:
return res
# 寻找-(a+b)是否在数组中，且下标小于b下标
for i in range(length-2):
for j in range(i+1, length-1):
num = -(nums[i] + nums[j])
index = d.get(num, -1)
if index == -1 or index <= j:
continue
else:
ls = [nums[i], nums[j], num]
min0 = min(ls)
max0 = max(ls)
new_element = [min0, -(min0+max0), max0]
if new_element not in res:
res.append(new_element)
return res我们换一种思路，如果将数组从小到大排序，那么第一层遍历nums[i]>0时，就可以不用再循环了；同时，两组数中，只要一组数的nums[i]及nums[j]和另一组数的不同，那么这两组数肯定不同，因此不用判断新的一组数是否存在于res中，时间复杂度为0(n^2)
class Solution(object):
def threeSum(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
length = len(nums)
res = []
# 数组元素个数必须要大于3
if length < 3:
return res
nums.sort()
# 字典，value为最后一个相同元素的下标
d = {}
for i in range(length):
d[nums[i]] = i
for i in range(length-2):
# 相同元素，不用再次遍历
if i > 0 and nums[i] == nums[i-1]:
continue
if nums[i] > 0:
break
for j in range(i+1, length-1):
# 相同元素，不用再次遍历
if j > i+1 and nums[j] == nums[j-1]:
continue
num = -(nums[i] + nums[j])
if num < nums[j]:
break
if d.get(num, -1) > j:
res.append([nums[i], nums[j], num])
return res这里介绍下字典的get方法，d.get(key, default=None)，通过键值key得到value，如果该key不存在，使用默认值default，因此在词频计数是可以使用如下代码：
def word_count(word)
'''
word:list
'''
res = {}
for w in word:
res[w] = res.get(w, 0) + 1
'''等同于：
if w in res:
res[w] += 1
else:
res[w] = 1
'''
return res相关文章：