-
Notifications
You must be signed in to change notification settings - Fork 0
/
1-Two-Sum.cpp
54 lines (40 loc) · 1.38 KB
/
1-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
// Author : Vicen-te
// Date : 17/10/2022
/*
Given an array of integers nums and an integer target,
return indices of the two numbers such that they add up to target.
You may assume that each input would have exactly one solution,
and you may not use the same element twice.
You can return the answer in any order.
Ex.
Input: nums = [2,7,11,15], target = 9
Output: [0,1]
1.- Insert into a new vector of two values the number and position of nums.
2.- Sort the vector by number (in order).
3.- Initialize the first and last position of the vector.
4.- Check if the number is greater or less than the target.
And it returns the position when the sum of the numbers matches the target.
Time: O(NlogN)
Space: O(N)
*/
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
vector<pair<int, int>> v;
for (int i = 0; i < nums.size(); i++)
v.push_back({ nums[i],i });
sort(v.begin(), v.end());
int i = 0;
int j = v.size() - 1;
while (i < j)
{
if (v[i].first + v[j].first == target)
return { v[i].second, v[j].second };
if (v[i].first + v[j].first < target)
i++;
if (v[i].first + v[j].first > target)
j--;
}
return { 0,0 };
}
};