1. Two Sum

1. Two Sum

Easy

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 <= 104
• -109 <= nums[i] <= 109
• -109 <= target <= 109
• Only one valid answer exists.

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

Hint:

1. A really brute force way would be to search for all possible pairs of numbers but that would be too slow. Again, it's best to try out brute force solutions for just for completeness. It is from these brute force solutions that you can come up with optimizations.
2. So, if we fix one of the numbers, say x, we have to scan the entire array to find the next number y which is value - x where value is the input parameter. Can we change our array somehow so that this search becomes faster?
3. The second train of thought is, without changing the array, can we use additional space somehow? Like maybe a hash map to speed up the search?

Solution:

To solve this problem, we can follow these steps:

Let's implement this solution in PHP: 1. Two Sum

<?php
// Test the function with example inputs
print_r(twoSum([2, 7, 11, 15], 9)); // Output: [0, 1]
print_r(twoSum([3, 2, 4], 6)); // Output: [1, 2]
print_r(twoSum([3, 3], 6)); // Output: [0, 1]
?>

Explanation:

1. Initialization:

   • Create an empty associative array $map to store the numbers and their indices.

2. Iteration:

   • Loop through the array using a foreach loop.
   • For each number, calculate its complement ($target - $num).

3. Check for Complement:

   • If the complement exists in the associative array (isset($map[$complement])), return the index of the complement and the current index.
   • If not, store the current number and its index in the associative array ($map[$num] = $index).

4. Return:

   • The function will return an array containing the indices of the two numbers that add up to the target.

This solution has a time complexity of (O(n)) and a space complexity of (O(n)), making it efficient for large input sizes.

Contact Links

If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks 😍. Your support would mean a lot to me!

If you want more helpful content like this, feel free to follow me:

• LinkedIn
• GitHub