C++

Forum

 
c++ indice 2 numbers

leo2008 (147)
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;
}
};
jonnin (11383)
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.

Last edited on
leo2008 (147)
Maybe a better approach is this way?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
 
#include <iostream>
#include<vector>
#include<algorithm>
using namespace std;

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
    for (int i = 0; i < nums.size(); i++) {
        for (int j = i + 1; j < nums.size(); j++) {
            if (nums[i] + nums[j] == target) {
                return {i, j};
            }
        }
    }
    return {};
  }
};
Last edited on
jonnin (11383)
brute force is ok for very small problems. Your algorithm is N*N, mine is just N (really, 2N, if you want to detail it out).

sometimes 'better' is less code. Sometimes 'better' is faster code. Your call on that.

Why is it in a class? Looks like java code turned to vinegar.
Last edited on
seeplus (6524)
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:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
 
#include <iostream>
#include <vector>

using Data = std::vector<int>;
using Result = std::vector<size_t>;

Result combo(const Data& c, int k, int req) {

	const auto check { [&req](const Data& c, unsigned combo) {
		Result res;
		int sum {};

		for (size_t i {}; (i < c.size()) && (sum < req); ++i)
			if ((combo >> i) & 1) {
				res.push_back(i);

				if (sum += c[i]; sum == req)
					return res;
			}

		return Result {};
	} };

	if (k <= c.size())
		for (auto combo { (1 << k) - 1 }; combo < 1 << c.size(); )
			if (const auto fnd { check(c, combo) }; fnd.empty()) {
				const auto x { combo & -combo };
				const auto y { combo + x };
				const auto z { combo & ~y };

				combo = z / x;
				combo >>= 1;
				combo |= y;
			} else
				return fnd;

	return Result {};
}

int main() {
	const Data c0 { 3, 2, 4 };

	if (const auto fnd { combo(c0, 2, 6) }; !fnd.empty()) {
		for (const auto& f : fnd)
			std::cout << f << ' ';

		std::cout << '\n';
	} else
		std::cout << "Mission impossible!\n";
}


This displays:


1 2

Registered users can post here. Sign in or register to post.