Problem Description
Given an integer array nums, find all unique pairs of indices i and j such that nums[i] + nums[j] == target.
Each number can be used only once, and index pairs (i, j) and (j, i) are considered the same combination, so they should not be counted multiple times.
For example, if the array is nums = [2, 7, 11, 15] and target = 9, the index pair to return should be [0, 1].
This is because nums[0] + nums[1] = 2 + 7 = 9.
Problem Analysis
An efficient method is required to solve this problem. Generally, using a nested loop results in a time complexity of O(n^2), which is inefficient for large arrays.
Therefore, we will introduce a way to reduce the time complexity to O(n) by using the two-pointer technique.
Understanding the Two-Pointer Technique
The two-pointer technique is a useful algorithmic method for processing arrays, where two pointers are used to solve the problem.
This technique allows us to simplify complex problems with arrays.
Let’s consider a simple example. Assume we want to find all combinations of two numbers in a sorted array that sum to a specific value (target).
Initially, place one pointer at the start of the array and the other at the end. If the sum of the values pointed to by the two pointers is greater than target,
move the right pointer one step to the left. On the other hand, if the sum is less than target, move the left pointer one step to the right.
By adjusting the pointers in this way, we can check all possible combinations.
Problem-Solving Process
I will explain the steps to solve the problem.
Step 1: Sort the Array
To apply the two-pointer technique, the array must be sorted. Sorting simplifies the comparison and movement of values at each pointer.
In a sorted array, each number can be found more quickly, and duplicate combinations can be prevented.
Step 2: Initialize Pointers
Initialize the pointers. One starts at the beginning (index 0), and the other starts at the end (length of the array – 1).
Step 3: Compare Sum and Move Pointers
– Repeat until the pointers cross each other.
– If the sum of the numbers pointed to by the current pointers is greater than target, move the right pointer one step to the left (i.e., choose a smaller value).
– If the sum is less than target, move the left pointer one step to the right (i.e., choose a larger value).
– If the sum equals target, record the indices and move both pointers.
Step 4: Return Results
After finding all possible combinations, return the list of index pairs.
Swift Code Implementation
Below is the Swift code implementing the algorithm described above.
swift
import Foundation
func twoSum(nums: [Int], target: Int) -> [[Int]] {
var result: [[Int]] = []
var numDict: [Int: Int] = [:]
for (index, num) in nums.enumerated() {
let complement = target - num
if let complementIndex = numDict[complement] {
result.append([complementIndex, index])
}
numDict[num] = index
}
return result
}
// Example usage
let nums = [2, 7, 11, 15]
let target = 9
let indices = twoSum(nums: nums, target: target)
print(indices) // Output: [[0, 1]]
Conclusion
The two-pointer technique is a powerful tool that reduces time complexity and provides better performance. This technique can be useful in many algorithm problems,
especially in finding the sum of two numbers in an array.
Through this lesson, I hope you learn how to solve algorithm problems using the Swift language, and further develop your ability to tackle various problems.
Additional Practice Problems
Try solving the following problems.
- Find all index pairs in a sorted array whose sum equals a specific value.
- Count the number of unique pairs in a sorted array.
- Find all intervals with a cumulative sum equal to a specific value.
- Find all pairs within a given range that includes a specified number.