1. Two Sum
🟩 Easy
Question
Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
Example:
Solution 1: Hash Table
Calculate the remainder
after subtracting element from target, if the remainder can be found in the loop up table, then we can get the index
and return the result. Otherwise, we add the current element to the table.
Time complexity: O(n)
Space complexity: O(n)
Solution 2: Two Pointers
Sort the input array in non-descending order, then use two pointers, one at the first element and one at the last. If the sum of two pointed elements is greater than the target value, move the right pointer to its left. Similarly, if the sum is less, move the left pointer to its right.
Time complexity: O(n log n)
Space complexity: O(1)
Code
Last updated
Was this helpful?