Initial Solution
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
for i in range(len(nums)-1):
for q in range(i+1, len(nums)):
if target == nums[i] + nums[q]:
return [i,q]
Python
복사
Time complexity and Space Complexity
Time Complexity: O(n²) - The nested loop iterates through all possible pairs of elements in the array, resulting in quadratic time complexity.
Space Complexity: O(1) - Only a constant amount of extra space is used for variables i and q.
What I didn’t know
•
I tried using two pointers but not working
◦
error on [-1, -2, -3, -4, -5]
Other Better Solutions
Hash Map Solution
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
seen = {}
for i, num in enumerate(nums):
complement = target - num
if complement in seen:
return [seen[complement], i]
seen[num] = i
Python
복사
This solution uses a hash map (dictionary) to store numbers we've seen along with their indices. For each number, we calculate what complement we need to reach the target, then check if we've already seen that complement.
If we find the complement in our hash map, we immediately return the indices. Otherwise, we add the current number and its index to the hash map and continue.
Time complexity and Space Complexity
Time Complexity: O(n) - The solution iterates through the array once, and hash map lookups and insertions are O(1) on average.
Space Complexity: O(n) - In the worst case, we might need to store all n elements in the hash map before finding the solution.