35657

Untitled

May 30th, 2024
499
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.96 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <fstream>
  4.  
  5. int main() {
  6.  
  7.  
  8.  
  9.     int count, number;
  10.  
  11.     std::ifstream fin("input.txt");
  12.  
  13.     fin >> count;
  14.  
  15.     std::vector<int> vec(count);
  16.  
  17.     for (int i = 0; i < count; i++) {
  18.         fin >> vec[i];
  19.     }
  20.  
  21.     fin >> number;
  22.  
  23.  
  24.     // 1 вариант - наивное решение за O(N^2)
  25.     /*for (int i = 0; i < count - 1; i++) {
  26.         for (int j = i + 1; j < count; j++) {
  27.             if (vec[i] + vec[j] == number) {
  28.                 std::cout << vec[i] << " " << vec[j] << std::endl;
  29.                 return 0;
  30.             }
  31.         }
  32.     }
  33.     std::cout << "None" << std::endl;*/
  34.  
  35.     // 2 вариант - метод двух указателей за O(N)
  36.  
  37.     int current_sum;
  38.  
  39.     int left = 0, right = count - 1;
  40.  
  41.     while (left < right) {
  42.         current_sum = vec[left] + vec[right];
  43.         if (current_sum == number) {
  44.             std::cout << vec[left] << " " << vec[right] << std::endl;
  45.             return 0;
  46.         }
  47.         current_sum < number ? left++ : right--;
  48.     }
  49.     std::cout << "None" << std::endl;
  50. }
Advertisement
Add Comment
Please, Sign In to add comment