Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <fstream>
- int main() {
- int count, number;
- std::ifstream fin("input.txt");
- fin >> count;
- std::vector<int> vec(count);
- for (int i = 0; i < count; i++) {
- fin >> vec[i];
- }
- fin >> number;
- // 1 вариант - наивное решение за O(N^2)
- /*for (int i = 0; i < count - 1; i++) {
- for (int j = i + 1; j < count; j++) {
- if (vec[i] + vec[j] == number) {
- std::cout << vec[i] << " " << vec[j] << std::endl;
- return 0;
- }
- }
- }
- std::cout << "None" << std::endl;*/
- // 2 вариант - метод двух указателей за O(N)
- int current_sum;
- int left = 0, right = count - 1;
- while (left < right) {
- current_sum = vec[left] + vec[right];
- if (current_sum == number) {
- std::cout << vec[left] << " " << vec[right] << std::endl;
- return 0;
- }
- current_sum < number ? left++ : right--;
- }
- std::cout << "None" << std::endl;
- }
Advertisement
Add Comment
Please, Sign In to add comment