C ++ twoSum。优化内存使用量

Question

我正在解决twoSum问题。步骤：

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();
}

Answer 1

您可以执行以下两项操作来最大程度地减少内存使用。首先，您不需要将文件的全部内容读入std::string。您可以直接读取std::vector，或者最好还是将文件内容读取到单个int变量中，并在处理过程中处理数字。另一件事：您不需要使用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;
}