Solution to LeetCode 1 Two Sum & LeetCode 454 4 Sum II
LeetCode 1
Two Sum (Easy) [link]
梦开始的地方。
This is where Dream started.
1] Brute Force Solution. Time complexity O(n^2). Space complexity O(1).
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
res = []
for i in range(len(nums)):
for j in range(i+1,len(nums)):
if nums[i] + nums[j] == target:
res.append(i)
res.append(j)
break
return res
2] HashTable. Iterate through all numbers in the list and determine whether ‘target - number’ is visited before. We use HashTable to store the number visited. Dictionary can be used to store index.
Time complexity O(n), space complexity O(n).
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
tab = dict()
for idx, num in enumerate(nums):
if target-num not in tab:
tab[num] = idx
else:
return [tab[target-num], idx]
LeetCode 454
4 Sum II (Medium) [link]
HashTable. Time complexity O(n^2). Space complexity O(n^2).
class Solution:
def fourSumCount(self, nums1: List[int], nums2: List[int], nums3: List[int], nums4: List[int]) -> int:
tab = dict()
for n1 in nums1:
for n2 in nums2:
if n1+n2 in tab:
tab[n1+n2] += 1
else:
tab[n1+n2] = 1
count = 0
for n3 in nums3:
for n4 in nums4:
key = -n3-n4
if key in tab:
count += tab[key] # there can be duplicates
return count
