LeetCode

Two Sum

Summary

Find the indices of two numbers such that they add up to the target.

Approach 1

Check all possible pairs.

Algorithm

For each element a at index i in nums, check each remaining element b after index i. If a + b == target, return both indices.

Complexity

Time complexity: O(N^2), because we check all pairs. Space complexity: O(1), because no extra space is needed.

Approach 2

Use a hash map to store values we have already seen. The bottleneck in Approach 1 is repeated checks of the same values.

Algorithm

Initialization:

• seen: key = number, value = index

Main loop: For each element a at index i in nums:

• If target - a is in seen, we have found the answer.
• Otherwise, add a and i to seen.

Complexity

Time complexity: O(N) Space complexity: O(N)