我是靠谱客的博主 妩媚红酒,这篇文章主要介绍【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

最后

以上就是妩媚红酒最近收集整理的关于【Leetcode打卡Day1】two sum总结的全部内容,更多相关【Leetcode打卡Day1】two内容请搜索靠谱客的其他文章。

本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
点赞(68)

评论列表共有 0 条评论

立即
投稿
返回
顶部