48 lines
1.2 KiB
C++
48 lines
1.2 KiB
C++
#include <vector>
|
|
#include <algorithm>
|
|
|
|
struct Pair {
|
|
int first;
|
|
int second;
|
|
|
|
Pair(int f, int s) : first(f), second(s) {}
|
|
Pair() : first(0), second(0) {}
|
|
bool operator>(const Pair& other) const {
|
|
return first > other.first;
|
|
}
|
|
bool operator<(const Pair& other) const {
|
|
return first < other.first;
|
|
}
|
|
};
|
|
|
|
class TwoSumSolution {
|
|
public:
|
|
std::vector<int> twoSum(std::vector<int>& nums, int target) {
|
|
std::vector<Pair> numPairs;
|
|
int i = 0;
|
|
for (auto num : nums) {
|
|
numPairs.emplace_back(num, i);
|
|
i++;
|
|
}
|
|
std::sort(numPairs.begin(), numPairs.end());
|
|
while (true)
|
|
{
|
|
int left = 0;
|
|
int right = static_cast<int>(numPairs.size()) - 1;
|
|
while (left < right) {
|
|
int sum = numPairs[left].first + numPairs[right].first;
|
|
if (sum == target) {
|
|
return std::vector<int>{numPairs[left].second, numPairs[right].second};
|
|
} else if (sum < target) {
|
|
left++;
|
|
} else {
|
|
right--;
|
|
}
|
|
}
|
|
break;
|
|
}
|
|
|
|
return std::vector<int>{};
|
|
}
|
|
};
|