The Two Sum problem is a popular coding interview question that asks you to find two numbers in an array that add up to a given target value. The problem statement typically provides an integer array and an integer . You need to find two elements in the nums array such that their sum equals and return their indices as an array.
For example, given an array and a target value , the function should return because .
The problem can be solved using various algorithms such as brute force, two-pass hash table, or one-pass hash table. The time and space complexity of the algorithm may vary based on the approach used.
Here’s a solution in Swift:
func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
var numDict = [Int: Int]()
for (i, num) in nums.enumerated() {
let complement = target - num
if let complementIndex = numDict[complement] {
return [complementIndex, i]
}
numDict[num] = i
}
fatalError("No two sum solution")
}
let nums = [2, 7, 11, 15]
let target = 18
print(twoSum(nums, target)) // [1, 2]
The time complexity of the above solution to the Two Sum problem is , where is the length of the input array nums. This is because the algorithm performs a single pass through the array, and for each element in the array, it performs a constant-time dictionary lookup operation to check if the complement of the current element exists in the dictionary.