The Two Sum problem is a classic coding challenge where you’re given an array of integers and a target number. Your task is to find two numbers in the array that add up to the target number. In this article, we’ll explore how to solve the Two Sum problem efficiently using Ruby, with detailed explanations and examples.
Approach 1: Brute Force Method
One approach to solve the Two Sum problem is to use a brute force method, where we iterate through the array and check every possible pair of numbers to see if their sum equals the target.
def two_sum(nums, target)
(0...nums.length).each do |i|
(i+1...nums.length).each do |j|
return [i, j] if nums[i] + nums[j] == target
end
end
end
nums = [2, 7, 11, 15]
target = 9
puts two_sum(nums, target) #=> [0, 1]
Approach 2: Using a Hash Map
A more efficient approach is to use a hash map to store the indices of elements as we iterate through the array. For each element num in the array, we calculate its complement (target - num) and check if it exists in the hash map. If it does, we’ve found the pair of numbers that add up to the target.
def two_sum(nums, target)
num_indices = {}
nums.each_with_index do |num, index|
complement = target - num
return [num_indices[complement], index] if num_indices.key?(complement)
num_indices[num] = index
end
end
nums = [2, 7, 11, 15]
target = 9
puts two_sum(nums, target) #=> [0, 1]
