-
Notifications
You must be signed in to change notification settings - Fork 5
/
Two_Sum.cpp
89 lines (68 loc) · 2.22 KB
/
Two_Sum.cpp
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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
/*
Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
Example:
Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1]. */
#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;
vector<int> result;
/* CODE TO GET VALUES WITHOUT THE USE OF VECTOR
class Solution {
public:
int twoSum(int nums[], int target) {
for(int i=0;i<sizeof(nums);i++)
{
int number = nums[i];
int new_targ = target - number;
for(int j=0 ; j<sizeof(nums);j++)
{
if(nums[j]==new_targ && j!=i && j < sizeof(nums) && i < j)
{
cout<<"["<<i<<","<<j<<"]";
}
}
}
}
};
int main()
{
Solution s;
int arr[] = {2,7,11,15};
s.twoSum(arr,9);
}
*/
// CODE WITH VECTOR MORE EFFICEINT WITH A AVERAGE RUNNING TIME OF O(1)
class Solution {
public:
vector<int> twoSum(vector<int> &numbers, int target) {
unordered_map<int, int> comp; // The syntax is kinda like this unordered_map<key,value> variable_name;
vector<int> result;
for(int i=0; i<numbers.size(); i++){
if (comp.find(numbers[i])==comp.end() ) { // m.find(key)==m.end() , This says if key is not there in the unordered_map array
// store the first one position into the second one's key
comp[target - numbers[i]] = i; // m[key] = value , comp stores the compliments of the given array. ex: m[7] = 0
}else {
// found the second one
result.push_back(comp[numbers[i]]); // Pushes the values of the complement array keys to result vector
result.push_back(i); // Pushes the current index number to result vector
break;
}
}
return result;
}
};
int main()
{
Solution s;
vector<int> arr = {2,7,11,15};
result = s.twoSum(arr,9);
for(int value:result) // Advanced for loop read as "For each value in result do this"
{
cout<< result[value];
}
return 0;
}