What is Two Pointers?
The two pointers technique is one of the methods for efficient algorithm design. This method is mainly useful for finding pairs of data or subarrays that satisfy specific conditions in sorted data structures. Essentially, it uses two pointers to point to the start and end of an array or two different elements, which helps solve the problem.
The two pointers technique allows us to solve various data problems with a time complexity of O(n). It is commonly used in problems involving consecutive arrays, sum problems, and subarray problems. This method is designed to find answers that meet the problem’s conditions by adjusting the positions of the two pointers.
Problem Description: Finding a Subarray with a Specific Sum
Problem: Given an integer array nums, write an algorithm to find two numbers that add up to a given integer target. Each element can be used only once. Return the indices of the two numbers in the form of an array.
Example Input:
nums = [2, 7, 11, 15], target = 9
Example Output:
[0, 1]
Explanation: nums[0] + nums[1] = 2 + 7 = 9.
Problem Solving Process
1. Understanding the Problem
The goal of this problem is to find the indices of two numbers in the given array. The key point of the problem is that each number can only be used once. Therefore, it is necessary to create combinations to find the specific sum.
2. Approach
We will use the two pointers technique to solve the problem. Even if we sort the array, we need to keep track of the original indices. Additionally, since the array is sorted, we can adjust the positions of the two pointers to find the optimal solution.
3. Algorithm Design
- Sort the array.
- Set up two pointers: one pointing to the first element of the array and the other to the last element.
- If the sum reaches
target, return the corresponding indices. - If the sum is less than
target, move the left pointer to the right to increase the sum. - If the sum is greater than
target, move the right pointer to the left to decrease the sum. - Repeat the above steps until the two pointers overlap.
4. C++ Code Implementation
#include
#include
#include
using namespace std;
vector twoSum(vector& nums, int target) {
unordered_map numMap;
vector result;
for (int i = 0; i < nums.size(); i++) {
int complement = target - nums[i];
if (numMap.find(complement) != numMap.end()) {
result.push_back(numMap[complement]);
result.push_back(i);
return result;
}
numMap[nums[i]] = i;
}
return result; // In case no result is found
}
int main() {
vector nums = {2, 7, 11, 15};
int target = 9;
vector indices = twoSum(nums, target);
cout << "[" << indices[0] << ", " << indices[1] << "]" << endl;
return 0;
}
5. Code Explanation
The above C++ code iterates through the given nums array to find the indices of the two numbers that can create the target value. It uses a hash map (unordered_map) to maintain a time complexity of O(n). Each time we select the first number, we check if its complement (target - nums[i]) exists in the hash map, and if it does, we return the two indices as the result.
The hash map allows for fast retrieval of each number, enabling an efficient way to find the answer by iterating through the array only once.
6. Complexity Analysis
The time complexity of the above algorithm is O(n) and the space complexity is O(n). The hash map records the complement numbers and allows for efficient searching. Since arrays are often unsorted, using a hash map for access is advantageous.
Conclusion
The two pointers technique is very useful in array problems. Finding two numbers that satisfy a specific sum in an unsorted array, like in this problem, is a frequently encountered issue. Using a hash map to optimize the algorithm is also a good strategy.
Practice solving various problems using the two pointers technique and try to extend and apply it to other issues.