LeetCode 1 - Two Sum - 2023.03.26 solution

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        """ Thought process:
        - It doesn't say the array is sorted.
        - O(n^2) solution is to check every combination of numbers.  You don't need to sort the array.
        - Sorting the array first could make the solution O(nlogn).

        Example: [-4, 1, 2, 4] and looking for 2.
        - Now for each number you can use binary search to look through the array to see if it has the particular
        number that would create the sum you're looking for.  This doesn't use any extra memory.  It's O(nlogn) to
        sort and then O(nlogn) use binary search for each number to look for its complement.

        But if you can use O(n) memory you can do it O(n) time.  You go through the array and for each element check a dict to see if you have its complement.  If you do, return the current index and the index of the complement.  If you don't, add this current element to the dict.
        """
        seen_values = dict()
        for index, num in enumerate(nums):
            if target - num in seen_values:
                return index, seen_values[target - num]
            else:
                seen_values[num] = index