Intuition

When first encountering the Two Sum problem, a straightforward approach might involve nested loops. For each element in the array, we could iterate through the remaining elements, checking if their sum equals the target. However, this approach would result in a time complexity of O(n^2).

Approach

To improve upon the brute-force approach, we can leverage a hash map (or dictionary in some languages). This allows us to efficiently check if a complement (target – current number) exists in the array.

Here’s a breakdown of the algorithm:

Create an empty hash map: This map will store the numbers we’ve encountered and their corresponding indices.
Iterate over the array:
For each number, calculate the complement needed to reach the target.
Check if the complement exists in the hash map.
If it does, return the indices of the current number and the complement.
If it doesn’t, add the current number and its index to the hash map.

Complexity

Time complexity: O(n)
We iterate through the array once, and each lookup in the hash map takes constant time on average.
Space complexity: O(n)
The hash map can store up to n elements in the worst case.

Problem

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

Example 1:

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

Example 2:

Input: nums = [3,2,4], target = 6
Output: [1,2]

Example 3:

Input: nums = [3,3], target = 6
Output: [0,1]

Constraints:

2 <= nums.length <= 10⁴
-10⁹ <= nums[i] <= 10⁹
-10⁹ <= target <= 10⁹
Only one valid answer exists.

Follow-up: Can you come up with an algorithm that is less than O(n²) time complexity?

source : CodeLeet

Code

class Solution {

    /**
     * @param Integer[] $nums
     * @param Integer $target
     * @return Integer[]
     */
    function twoSum($nums, $target) {
        $seen = [];
    for ($i = 0; $i < count($nums); $i++) {
        $complement = $target - $nums[$i];
        if (isset($seen[$complement])) {
            return [$seen[$complement], $i];
        }
        $seen[$nums[$i]] = $i;
    }
    return null;
    
    }
}

GitHub Source code

Explanation

The $seen array acts as a hash map, storing numbers as keys and their indices as values.
We iterate through the nums array.
For each number, we calculate the complement needed to reach the target.
If the complement is found in the $seen array, we’ve found a pair that adds up to the target.
If the complement is not found, we add the current number and its index to the $seen array for future comparisons.
In conclusion, this approach effectively solves the Two Sum problem with optimal time and space complexity. By utilizing a hash map, we can efficiently check for complements and avoid unnecessary nested loops.

Nader Yari

A Comprehensive Guide to the Two Sum Problem in PHP