I solved the below problem. Can anyone tell me the best way here?
Given a list of integers and a target sum, write a function to find the indices of the two numbers in the list that add up to the target sum. You may assume that each input would have exactly one solution, and you may not use the same element twice.
Example:
int[] nums = {3, 2, 4}
target=6;
Output: [1, 2]
#include <iostream>
#include<vector>
#include<algorithm>
using namespace std;
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
int n = (int)(nums.size());
vector<pair<int, int>> pairs;
for (int i = 0; i < n; i++) {
pairs.push_back({nums[i], i});
}
sort(pairs.begin(), pairs.end());
int left = 0, right = n - 1;
vector<int> ans;
while (left < right) {
int sum = pairs[left].first + pairs[right].first;
if (sum == target) {
ans.push_back(pairs[left].second);
ans.push_back(pairs[right].second);
break;
} else if (sum < target)
left++;
else
right--;
}
return ans;
}
};
the best way would be to load a hash table of the data (this hash table would have the value AND its original array location in its data fields as a tuple or something). Then randomly select 1 element, and ask the hash table if it contains the value (desired - randomselected). If it does, those two are the correct pairing and you are successful. If not, remove the randomly selected item from the hash table, and repeat this process.
for your example:
hash table has
value, location pairs:
3 0
2 1
4 2
and you randomly select.. the 3.
the desired value is 6.
6-3 is 3. you may not use the selected element, a second 3 does not exist, so remove the element from the table.
now it randomly picks the 2 or the 4.
6-2 is 4, search the table, yes there is a 4, so the answer is the 2's index (1) and the 4's index (2).
if the input data can have repeats, you must hash-key off both the value and its position. If the data can't have repeats, removal after random selection will prevent the 3+3=6 problem and work without additional logic. The additional logic is simply to ensure you don't use the same element twice.
This solution does not scale well to the problem of adding 3 items and finding the sum, or 4, or N.
Another way is to use combinations. Consider this which will find the indices of the vector whose sum is the required using the specified number of elements: