C ++ twoSum. Оптимизировать использование памяти - PullRequest
Новая
       116

C ++ twoSum. Оптимизировать использование памяти

0 голосов
/ 30 мая 2020

Я решаю задачу о двух суммах. Шаги:

  1. Прочтите входной файл со следующим шаблоном: 
   7
   1 7 3 4 7 9

Первая строка - целевой номер, вторая строка - числовая последовательность.

Числа могут быть в диапазоне 0

Если сумма двух чисел из числовой последовательности равна целевому числу, я записываю «1» в выходной файл.

Если нет чисел, сумма которых равна целевому числу, тогда я записываю «0» в выходной файл.

Мне нужно оптимизировать использование памяти в моем коде. Как я могу это сделать? 

#include <iostream>
#include <fstream>
#include <sstream>
#include <vector>
#include <unordered_map>
#include <string>
#include <algorithm>

using namespace std;

int main() {

ifstream f1;
vector<int> nums;
string line;
string source;
//Open input file and read it to a string
f1.open("input.txt");
while (getline(f1, line, '\n')) {
    source+=line + " ";
    } f1.close();

//Parse the string into an int vector
stringstream parser(source);
int num;
while (parser >> num) { nums.push_back(num); }

//Clear used strings
line = "";
source = "";

//Get target number
int target = nums.at(0);

//Get number sequence
nums.erase(nums.begin());
bool flag = false;

//Check number sequence for two numbers sum of which equals the target number

unordered_map<int, int> mp;

for(int i=0;i<nums.size();i++){
  if(mp.count(nums[i])==1){
    flag = true;
    break;}
  mp[target-nums[i]]=i;
  }

//Write the result into the output file
ofstream f2;
f2.open("output.txt");
f2 << flag;
f2.close();
}

1 Ответ

0 голосов
/ 30 мая 2020

Здесь вы можете сделать несколько вещей, чтобы минимизировать использование памяти. Во-первых, вам не нужно читать все содержимое файла в std::string. Вы можете читать непосредственно в std::vector или, еще лучше, читать содержимое файла в единственную переменную int и обрабатывать числа так же, как go. Другое дело: вам не нужно использовать std::unordered_map, потому что наличие ключа - единственное, что вас действительно интересует, поэтому std::unordered_set достаточно. Ниже представлено простое решение, использующее эти предложения: 

#include <fstream>
#include <unordered_set>

int main() {
    std::ifstream input {"input.txt"};

    int target;
    input >> target;
    int current_number;
    bool found = false;
    std::unordered_set<int> observed_numbers;
    while (input >> current_number) {
        if (observed_numbers.count(target - current_number) > 0) {
            found = true;
            break;
        }
        observed_numbers.insert(current_number);
    }
    std::ofstream output {"output.txt"};
    output << found;
}
...