diff options
Diffstat (limited to 'other/two_sum_2.cpp')
-rw-r--r-- | other/two_sum_2.cpp | 33 |
1 files changed, 33 insertions, 0 deletions
diff --git a/other/two_sum_2.cpp b/other/two_sum_2.cpp new file mode 100644 index 0000000..55741ac --- /dev/null +++ b/other/two_sum_2.cpp @@ -0,0 +1,33 @@ +#include "leetcode.h" +#include <vector> + +class Solution { +public: + vector<int> twoSum(vector<int> &numbers, int target) { + vector<int> ans; + for (int i = 0; i < numbers.size(); i++) { + int low = 0, high = numbers.size() - 1; + while (low <= high) { + int mid = low + (high - low) / 2; + if (numbers[mid] == target - numbers[i]) { + if (mid == i) + low = mid + 1; + else + return {i + 1, mid + 1}; + } else if (numbers[mid] < target - numbers[i]) + low = mid + 1; + else + high = mid - 1; + } + } + return ans; + } +}; + +int main() { + Solution obj; + vector<int> numbers = {2, 7, 11, 15}; + int target = 9; + // expected output: 1,2 + obj.twoSum(numbers, target); +} |