【Leetcode打卡Day1】two sum总结

103 阅读 0 评论 68 点赞

我是靠谱客的博主妩媚红酒，这篇文章主要介绍【Leetcode打卡Day1】two sum总结，现在分享给大家，希望可以做个参考。

【写在前面：还在上学，七月入职，实在太闲，小记一下，菜猫一只，欢迎交流。】

今天第一天，从第一题刷起，大名鼎鼎的two sum，在这里总结一下所有变形题。

【1. two sum】

解法：

1. brute force: loop through each element x by using two for loop.

time complexity: O(n^2), n is the length of the array
space complexity: O(1)

复制代码

1
2
3
4
5
6
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
for i in range(len(nums)):
for j in range(i+1, (len(nums))):
if nums[i]+nums[j] == target:
return [i,j]

2. Hash table

time complexity: O(n), n is the length of the array
space complexity: O(n), for the hash table, n is the length of the array

复制代码

1
2
3
4
5
6
7
8
9
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
m = {}
for i,v in enumerate(nums):
diff = target - v
if diff in m:
return [m[diff],i]
if v not in m:
m[v] = i

小结：比较简单，但这里初步体现了有时候TC和SC的tradeoff。

【167.Two Sum II - Input Array Is Sorted】

解法：看到sorted array，就要想到binary search和two pointer的解法。此题很容易想到可以用two pointer解。

1. brute force不提了, 同上

2. two pointer:

time complexity: O(n), n is the length of the array. In the worst case, we will need to traverse the whole array.
space complexity: O(1), constant space for two pointers

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
def twoSum(self, numbers: List[int], target: int) -> List[int]:
l, r = 0, len(numbers)-1
while l<r:
cursum = numbers[l] + numbers[r]
if cursum == target:
return [l+1,r+1] # 此题要求返还的是index+1
if cursum < target:
l+=1
else:
r-=1

【170. Two Sum III - Data structure design】

解法：原理和第一题相似

1. Array：暂时懒得写。。

2. hash map:

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class TwoSum:
def __init__(self):
self.map = {}
def add(self, number: int) -> None:
if number not in self.map:
self.map[number] = 1
else:
self.map[number] +=1
def find(self, value: int) -> bool:
for i in self.map:
diff = value - i
if i != diff:
if diff in self.map:
return True
elif self.map[diff]>1:
return True
return False

【653. Two Sum IV - Input is a BST】

解法：对于树的遍历问题，一般有dfs和bfs两种解法。

1. dfs:

time complexity: O(n), travase the whole tree at the worst case.
space complexity: O(n), space for the set

复制代码

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
# Definition for a binary tree node.
# class TreeNode:
#
def __init__(self, val=0, left=None, right=None):
#
self.val = val
#
self.left = left
#
self.right = right
class Solution:
def findTarget(self, root: Optional[TreeNode], k: int) -> bool:
visit= set()
stack = []
while stack or root:
while root:
stack.append(root)
root = root.left
root = stack.pop()
diff = k - root.val
if diff in visit:
return True
visit.add(root.val)
root = root.right
return False

2. bfs:

time complexity: O(n), travase the whole tree at the worst case.
space complexity: O(n), space for the set

复制代码

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
# Definition for a binary tree node.
# class TreeNode:
#
def __init__(self, val=0, left=None, right=None):
#
self.val = val
#
self.left = left
#
self.right = right
class Solution:
def findTarget(self, root: Optional[TreeNode], k: int) -> bool:
visit= set()
q = collections.deque()
q.append(root)
while q:
qlen = len(q)
for i in range(qlen):
node = q.popleft()
diff = k - node.val
if diff in visit:
return True
visit.add(node.val)
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
return False

【1099. Two Sum Less Than K】

解法：sort之后，two pointer; 因为要记录max sum less than k, 还要有一个variable来记录current max。

time complexity: O(n), n is the length of the array. In the worst case, we will need to traverse the whole array.
space complexity: O(1), constant space for two pointers

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
def twoSumLessThanK(self, nums: List[int], k: int) -> int:
nums = sorted(nums)
p1, p2 = 0, len(nums)-1
curmax = -1
while p1<p2:
cur = nums[p1]+nums[p2]
if cur < k:
p1+=1
curmax = max(curmax, cur)
else:
p2-=1
return curmax