1 15题描述

给定一个数组，从中选出三个数abc，使得：a+b+c = 0，且选出的方案不得重复！

2 我的解答，三种都超时~

# 15题
# 注意：一个元素在一个方案中不可以重复出现！
# 暴力解法：严重超时!O(n^3)
class Solution:
def threeSum(nums):
l = len(nums)
ans = []
map_ans = []
for a in range(l):
for b in range(a+1, l):
for c in range(b+1, l):
tmp_list = [nums[a], nums[b], nums[c]]
if sum(tmp_list) == 0:
#
print(tmp_list)
tmp_set = set(tmp_list)
if tmp_set not in map_ans:
map_ans.append(tmp_set)
ans.append(tmp_list)
return ans

# 15题
# 注意：一个元素在一个方案中不可以重复出现！
# 先找两个数，还是超时。。。。因为没有定义哈希表，复杂度不变！
class Solution:
def threeSum(nums):
l = len(nums)
ans = []
map_ans = []
for a in range(l):
for b in range(a+1, l):
z1, z2, z3 = nums[a], nums[b], 0-nums[a]-nums[b]
if z3 in nums:
index = nums.index(z3)
tmp_list = [z1, z2, z3]
tmp = set(tmp_list)
if tmp not in map_ans and index != a and index != b:
map_ans.append(tmp)
ans.append(tmp_list)
return ans

# 15题
# 注意：一个元素在一个方案中不可以重复出现！
# 一定要定义一个哈希表
# 还是超时。。。。
class Solution:
def threeSum(nums):
l = len(nums)
# 注意考虑特殊情况！
if len(nums) < 3:
return []
res = set()
d = {}
for v in nums:
if v in d:
d[v] += 1
else:
d[v] = 1
#
print(d)
for i in range(l):
for j in range(i+1, l):
#
d.copy(dd)
a, b, c = nums[i], nums[j], -nums[i]-nums[j]
#
print()
#
print(z3, end = ' ')
#
print(a, b, c)
if c in d:
tmp = {}
tmp[a] = d[a]
tmp[b] = d[b]
tmp[c] = d[c]
tmp[a] -= 1
tmp[b] -= 1
tmp[c] -= 1
#
print(a,'-',tmp[a] , b,'-', tmp[b] , c,'-', tmp[c])
if tmp[a] >= 0 and tmp[b] >= 0 and tmp[c] >= 0:
res.add(tuple(sorted([a, b, c])))
return list(map(list, res))

3 大佬（薛玉洁）解答

# Time: O(n^2)
# Space: O(1) or O(n) depending on extra memory needed for sorting
class Solution:
def threeSum(nums):
res = []
nums.sort()
# 从这里开始是一个三指针问题
for i, a in enumerate(nums):
if i > 0 and a == nums[i - 1]:# 防止选到的a重复
continue
# 从这里开始是一个双指针问题
l, r = i + 1, len(nums) - 1
while l < r:
threeSum = a + nums[l] + nums[r]
if threeSum > 0:
r -= 1
elif threeSum < 0:
l += 1
else:
res.append([a, nums[l], nums[r]])
l += 1
while nums[l] == nums[l - 1] and l < r:
# 上一句解释：当当前组a确定的时候，避免b和上一组答案重复，
# c不需要判断，因为ab一旦确定不和上一组一样，那么当前组就一定不会和上一组重复了！！
l += 1
return res

最后

以上就是英俊蜜粉为你收集整理的数据结构之leetcode 15题1 15题描述2 我的解答，三种都超时~3 大佬（薛玉洁）解答的全部内容，希望文章能够帮你解决数据结构之leetcode 15题1 15题描述2 我的解答，三种都超时~3 大佬（薛玉洁）解答所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。