Sponsored
Sponsored
This approach leverages a hash map (or dictionary) to solve the problem efficiently. By taking advantage of the average O(1) time complexity for insert and lookup operations in hash maps, we can create a mapping between elements and their indices (or frequencies, depending on the problem requirements). This method not only offers efficient retrieval but also makes it easier to track elements as we iterate through the data structure.
Time Complexity: O(n), where n is the number of elements in the input list.
Space Complexity: O(n), due to the storage of numbers in the hash map.
#include <vector>
using namespace std;
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int, int> numMap;
for (int i = 0; i < nums.size(); i++) {
int complement = target - nums[i];
if (numMap.find(complement) != numMap.end()) {
return {numMap[complement], i};
}
numMap[nums[i]] = i;
}
return {};
}This C++ solution uses an unordered_map to keep track of numbers and their indices. Similar to the previous approaches, it checks for the presence of the complement in the map and returns the indices if found.
This approach utilizes a two-pointer technique which is particularly effective when the input is sorted (or can be sorted) without significantly impacting performance. By using two pointers to traverse the array from both ends, we can efficiently find the pair of elements that sum to the target. Note that this approach is based on the assumption that sorting the input is feasible and will not exceed time limits.
Time Complexity: O(n log n) due to sorting.
Space Complexity: O(n) because we store tuples of indices and numbers.
1import java.util.Arrays;
2
3public int[] twoSum(int[] nums, int target) {
4 int[][] numsWithIndexes = new int[nums.length][2];
5 for (int i = 0; i < nums.length; i++) {
6 numsWithIndexes[i][0] = nums[i];
7 numsWithIndexes[i][1] = i;
8 }
9 Arrays.sort(numsWithIndexes, (a, b) -> a[0] - b[0]);
10 int left = 0, right = numsWithIndexes.length - 1;
11 while (left < right) {
12 int sum = numsWithIndexes[left][0] + numsWithIndexes[right][0];
13 if (sum == target) {
14 return new int[] { numsWithIndexes[left][1], numsWithIndexes[right][1] };
15 } else if (sum < target) {
16 left++;
17 } else {
18 right--;
19 }
20 }
21 return new int[] {};
22}In this Java implementation, an array of arrays is used to keep track of the numbers and their original indices. After sorting, two pointers are managed to find the solution.