[LeetCode] 1. Two Sum

Problem : https://leetcode.com/problems/two-sum/

With the formula "A + B = Target" in mind,  the problem basically equals to by given number A search number B in the array.

Solution1, Binarch search based solution

Time Complexity = O(N + N*LogN + N * LogN) = O (N * LogN)
Space Complexity = O(N), for the space used by the sorted array.

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        sortedNums = sorted([(n, i) for i, n in enumerate(nums)])
    
        def bsearch(left, right, target):
            while left < right:
                mid = left + (right - left) // 2
                
                if sortedNums[mid][0] == target:
                    return sortedNums[mid][1]
                
                elif sortedNums[mid][0] < target:
                    left = mid + 1
                else:
                    right = mid
            
            return -1
        
        for si, (n, i) in enumerate(sortedNums):
            j = bsearch(si+1, len(sortedNums), target - n)
            if j != -1:
                return [i, j]

Solution 2, Two-pointers based solutin:

Time Complexity = O(N + N * Log N + LogN) = O ( N * Log N )
Space Complexity = O(N), for the space used by the sorted array.

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        sortedNums = sorted([(n, i) for i, n in enumerate(nums)])
    
        left, right = 0, len(sortedNums) - 1
        
        while left < right:
            sums = sortedNums[left][0] + sortedNums[right][0]
            
            if sums == target:
                return sortedNums[left][1], sortedNums[right][1]
            
            if sums < target:
                left += 1
            else:
                right -= 1

Solution 3, use hash table to save all encountered number and its index. Return the corresponding indices when 'target - n' is found in the hash table.

Time Complexity = O(N)
Space Complexity = O(N), for space used by hash map.

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        seen = {}
        
        for i, n in enumerate(nums):
            if target - n in seen: 
                return [seen[target -n], i]
            else:
                seen[n] = i