The Two-Sum Problem Fast AF
The Two-Sum Problem is a common programming problem that involves finding two numbers in an array that add up to a given target number. It is often used as a warm-up problem to practice algorithms and data structures. In this tutorial, we will explore multiple ways to solve the Two-Sum Problem in Swift and understand how they work.
Solution 1: Brute Force
The brute force approach involves looping through the array and checking every possible combination of two numbers. This is the most basic and straightforward solution, but it has a time complexity of O(n²), which means it will be slow for larger arrays.
Here is the code for the brute force solution in Swift:
func twoSumBruteForce(nums: [Int], target: Int) -> [Int] {
for i in 0..<nums.count {
for j in (i+1)..<nums.count {
if nums[i] + nums[j] == target {
return [i, j]
}
}
}
return []
}To test this solution, we can create an array of integers and a target number, and then call the twoSumBruteForce function:
let nums = [2, 7, 11, 15]
let target = 9
print(twoSumBruteForce(nums: nums, target: target)) // [0, 1]Solution 2: Hash Table
A more efficient solution is to use a hash table, also known as a dictionary in Swift. We can loop through the array once and add each number and its index to the dictionary. Then, for each number, we can check if the target minus that number exists in the dictionary. If it does, we have found the two numbers that add up to the target. This solution has a time complexity of O(n) because we only loop through the array once.
Here is the code for the hash table solution in Swift:
func twoSumHashTable(nums: [Int], target: Int) -> [Int] {
var dict = [Int: Int]()
for i in 0..<nums.count {
dict[nums[i]] = i
}
for i in 0..<nums.count {
let complement = target - nums[i]
if let index = dict[complement], index != i {
return [i, index]
}
}
return []
}To test this solution, we can use the same array and target as before and call the twoSumHashTable function:
print(twoSumHashTable(nums: nums, target: target)) // [0, 1]Solution 3: Two-Pointer
For sorted arrays, we can use a two-pointer approach to find the two numbers that add up to the target. We start with two pointers, one at the beginning of the array and one at the end. If the sum of the numbers at the two pointers is greater than the target, we move the right pointer to the left. If the sum is less than the target, we move the left pointer to the right. This continues until we find the two numbers that add up to the target or until the pointers meet. This solution has a time complexity of O(n) because we only loop through the array once.
Here is the code for the two-pointer solution in Swift:
func twoSumTwoPointer(nums: [Int], target: Int) -> [Int] {
var left = 0
var right = nums.count - 1
while left < right {
let sum = nums[left] + nums[right]
if sum == target {
return [left, right]
} else if sum < target {
left += 1
} else {
right -= 1
}
}
return []
}To test this solution, we can use the same array and target as before, but first we need to sort the array. We can do this using the sort() method in Swift:
let sortedNums = nums.sorted()
print(twoSumTwoPointer(nums: sortedNums, target: target)) // [0, 3]Note that the result of this solution will be different from the previous ones because the array is sorted.
Conclusion
In this tutorial, we explored three different ways to solve the Two-Sum Problem in Swift: brute force, hash table, and two-pointer. Each solution has its own time complexity and trade-offs, and it’s important to choose the right one depending on the specific problem you are trying to solve.
For more information on the Two-Sum Problem and other algorithms and data structures, you can check out the following resources:
