-
Notifications
You must be signed in to change notification settings - Fork 0
/
Solution.cpp
65 lines (51 loc) · 1.41 KB
/
Solution.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
#include "../StandardHeaders.hpp"
using namespace std;
class Solution
{
public:
vector<int> twoNumberSum(vector<int> array, int targetSum) {
return twoNumberSum_2(array, targetSum);
}
// Naive: O(n^2) nested loop to test all combinations
vector<int> twoNumberSum_1(vector<int> array, int targetSum) {
vector<int> ans;
for(int i=0; i<array.size()-1; i++){
for(int j=i+1; j<array.size(); j++){
if(array[i]+array[j]==targetSum){
ans.push_back(array[i]);
ans.push_back(array[j]);
}
}
}
return ans;
}
// Optimal time - O(n) time, O(n) space: use a set to store the differences with target sum
vector<int> twoNumberSum_2(vector<int> array, int targetSum) {
unordered_set<int> set;
for(int n:array){
int match = targetSum - n;
if(set.find(match) != set.end()){
return vector<int>{match, n};
} else {
set.insert(n);
}
}
return {};
}
// Optimal space - O(n log n) time, O(1) space: sort the input and scan with two l/r pointers
vector<int> twoNumberSum_3(vector<int> array, int targetSum) {
sort(array.begin(), array.end());
int l=0, r=array.size()-1;
while(l<r){
int sum = array[l] + array[r];
if( sum == targetSum){
return {array[l], array[r]};
} else if (sum > targetSum) {
r--;
} else {
l++;
}
}
return {};
}
};