I am not an expert in C++ but I can give a feedback about the Python solution.
Your current solution runs in \$O(n^2)\$. Basically, for each number n
of the input nums
, find target - n
in nums
. How to improved it?
The second part of the algorithm can be improved from \$O(n)\$ to \$O(1)\$. Instead of looking up target - n
in a list, you can use a dictionary:
def twoSumtwo_sum(self, nums: List[int]list, target: int) -> List[int]:
num_index = {}
for i, n in enumerate(nums):
match = target - n
if match in num_index:
return num_index[match], i
num_index[n] = i
return -1
Results:
Original: Runtime: 772 ms. Memory Usage: 14.4 MB
Improved: Runtime: 48 ms. Memory Usage: 15.5 MB