Leetcode 1. Two Sum, 15. 3Sum, 16. 3Sum Closest解题报告

Two Sum

  • 问题描述:

    给定一个整型的数组,返回和为指定值的两个元素的下标,可以假设只有一个答案。

这个问题写出解决代码很简单,第一想法就是两层遍历,先遍历前len(nums)-1个元素,再遍历对应的剩余元素。这种解法很直白,但是时间复杂度为O(n*n), 果然是提示时间超限的,所以要想办法降低时间复杂度.

如果引入一个存储已经遍历元素的buffer dict就能将时间复杂度降为O(n),具体代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
if len(nums) <= 1:
return False
buff_dict = {}
for i in range(len(nums)):
if nums[i] in buff_dict:
return [buff_dict[nums[i]], i]
else:
buff_dict[target - nums[i]] = i
  • 代码分析:
    使用buff_dict存储已经遍历过的元素以及与该元素的和为制定值的解,这样的话如果以后遍历的元素为已经遍历的元素的解,那么这个元素就已经在字典里了。

3Sum

  • 问题描述:

    给定一个整型数组,检测其中是否有三个元素的和为0,返回所有符合要求的三个元素组成的数组。

在解决这个问题时,如果想起了Two Sum的解法,可能就会走弯路了。。下面上时间复杂度为O(n*n)的解法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution():
def threeSum(self, nums):
nums.sort()
res = []
for i in range(len(nums) - 2):
if i > 0 and nums[i] == nums[i-1]:
continue
l = i + 1
r = len(nums) - 1
while l < r:
sum_result = nums[i] + nums[l] + nums[r]
if sum_result < 0:
l = l + 1
elif sum_result > 0:
r = r - 1
else:
res.append([nums[i], nums[l], nums[r]])
while l < r and nums[l] == nums[l+1]:
l += 1
while l < r and nums[r] == nums[r-1]:
r -= 1
l += 1; r -= 1
return res
  • 代码分析:
    没有什么好说的,这种问题就应该用这种解法,简单明了。

3Sum Closest

  • 问题描述:
    给定一个整型数组,找到数组中的三个元素,使三者的和最接近与一个给定值。返回三者的和。可以假设满足要求的元素只有一组。

这个问题和3Sum问题解法一样,下面上时间复杂度为O(n*n)的解法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution(object):
def threeSumClosest(self, nums, target):
if len(nums) < 3:
return None
nums.sort()
res = nums[0] + nums[1] + nums[2]
for i in range(len(nums)-2):
l, r = i+1, len(nums)-1
while l < r:
s = nums[i] + nums[l] + nums[r]
if s == target:
return s
if abs(s - target) < abs(res - target):
res = s
if s < target:
l += 1
elif s > target:
r -= 1
return res

要耳聪目明才能吃嘛嘛香啊!

  • 本文作者: 大护法
  • 本文链接: https://todebug.com/summary-of-threeSum/
  • 版权声明: 本博客所有文章除特别声明外,均采用 BY-NC-SA 4.0 许可协议。转载请注明出处!
0%