1.two-sum.md

1. Two Sum

Hash Table

For every number, we check if we have seen the complement number before.

def twoSum(self, nums: List[int], target: int) -> List[int]:
    map = {}
    for i in range(0, len(nums)):
        complement = target - nums[i]
        if complement in map:
            return [map[complement], i]
        map[nums[i]] = i
    return []

fun twoSum(nums: IntArray, target: Int): IntArray {
    val results = IntArray(2)
    // value, index
    val map = hashMapOf<Int, Int>()
    for (i in 0 until nums.size) {
        val num = nums[i]
        val complement = target - num
        
        if (complement in map) {
            results[0] = i
            results[1] = map[complement]!!
            break
        } else {
            map[num] = i
        }
    }
    return results
}

• Time Complexity: O(n) for only one for-loop.
• Space Complexity: O(n) for hash table.

Sorting + Two Pointers

Same as 167. Two Sum II - Input Array Is Sorted.