Readable Python solution [42ms]


  • 0
    class Solution(object):
        def twoSum(self, nums, target):
            """
            :type nums: List[int]
            :type target: int
            :rtype: List[int]
            
            Time: O(n * log(n))
            Space: O(n)
            
            """
            # Time: O(n * log(n))
            # Space: O(n)
            lookup_table = dict((n, i) for i, n in enumerate(nums))
            lookup = lookup_table.get
            
            # Find the matching number to sum up to target
            # Time: O(n * log(n))
            # Space: O(1)
            for i, n in enumerate(nums):
                j = lookup(target - n)
                if j is not None and i != j:
                    return (i, j)
    

  • 0

    Another solution based on sorting the numbers, then finding the pair with bidirectional searching [43ms]:

    class Solution(object):
        def twoSum(self, nums, target):
            """
            :type nums: List[int]
            :type target: int
            :rtype: List[int]
            
            Time: O(n * log(n))
            Space: O(n)
            
            """
            # Sorted indices
            si = range(len(nums))
            si.sort(key=lambda i: nums[i])
            
            # Bidirectional search for suitable (a, b) pair, so a + b == target
            i = 0
            j = len(nums) - 1
            while i < j:
                delta = nums[si[i]] + nums[si[j]] - target
                if delta > 0:
                    j -= 1
                elif delta < 0:
                    i += 1
                else:
                    return (si[i], si[j])
    

    It has practically the same complexity and speed as the first solution above. Memory consumption is more predictable due to the use of sorted list instead of dict (hash table).


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.