Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <unordered_map>
- using namespace std;
- // Run-time complexity O(n2)
- // Memory complexity O(n)
- vector<int> find_indexes(const vector<int>& nums, int sum) {
- unordered_map<int, int> hashmap;
- unordered_map<int, int> hashmap_index;
- vector<int> result;
- for (int i = 0; i < nums.size(); ++i) {
- int current = nums[i];
- for (auto item : hashmap) {
- int complement = sum - current - item.first;
- if (hashmap.count(complement) != 0) {
- if ((item.first == complement && item.second > 1) || item.first != complement) {
- result.push_back(i);
- result.push_back(hashmap_index[item.first]);
- result.push_back(hashmap_index[complement]);
- return result;
- }
- }
- }
- ++hashmap[current];
- hashmap_index[current] = i;
- }
- return result;
- }
- // Run-time complexity O(n2)
- // Memory complexity O(n)
- vector<int> find_values(const vector<int>& nums, int sum) {
- unordered_map<int, int> hashmap;
- vector<int> result;
- for (int num : nums) {
- for (auto item : hashmap) {
- int complement = sum - num - item.first;
- if (hashmap.count(complement) != 0) {
- if ((item.first == complement && item.second > 1) || item.first != complement) {
- result.push_back(num);
- result.push_back(item.first);
- result.push_back(complement);
- return result;
- }
- }
- }
- ++hashmap[num];
- }
- return result;
- }
- void print_vector(const vector<int>& vec) {
- for (int i = 0; i < vec.size(); ++i) {
- std::cout << vec[i] << std::endl;
- }
- }
- int main()
- {
- vector<int> v1 = {1 ,2 ,3 ,4 ,1 ,6};
- int sum1 = 5;
- vector<int> v2 = {1 ,2 ,3 ,4 ,1 ,6, 1, 2, 4, 1, 2, 6, 7, 10};
- int sum2 = 10;
- print_vector(v1);
- std::cout << std::endl;
- std::cout << sum1 << std::endl << "Values:" << std::endl;
- print_vector(find_values(v1, sum1));
- std::cout << "Indexes:" << std::endl;
- print_vector(find_indexes(v1, sum1));
- std:cout << "---------------" << std::endl;
- print_vector(v2);
- std::cout << std::endl;
- std::cout << sum2 << std::endl << "Values:" << std::endl;
- print_vector(find_values(v2, sum2));
- std::cout << "Indexes:" << std::endl;
- print_vector(find_indexes(v2, sum2));
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement