1

这是我要解决的问题：

写入findTwoSumPair，它接受一个整数向量和一个目标总和，并返回一对表示元素的两个不同索引，总和为目标值（索引已排序）。这里没有明确的时间复杂度限制（即算法只需要按预期工作）。还要确保处理空输入。

这是我的主要内容：

  std::cout << "Q3" << std::endl;
  std::vector<int> q3Input1{0, 2, 3, 4, 5};
  std::pair<int, int> q3Out1 = findTwoSumPair(q3Input1, 6);
  std::pair<int, int> q3Out2 = findTwoSumPair(q3Input1, 10);

  std::cout << q3Out1.first << " " << q3Out1.second
            << std::endl;  // should output 1 3
  std::cout << q3Out2.first << " " << q3Out2.second
            << std::endl;  // should output -1 -1

这是导致我出现问题的功能：

std::pair<int, int> findTwoSumPair(const std::vector<int>& vec, int targetSum) {
  for (unsigned int i = 0; i < vec.size(); i++){

    for(unsigned int j = i; i < vec.size();j++){
     /* 
      if(targetSum == vec[i]+ vec[j]){
      std::cout << vec[i] << vec[j];
      }*/
    }
  }
  return{vec[i],vec[j];
 // throw std::logic_error("not implemented");
}

我得到了 main.cpp，所以我不想更改它，并且有相关的库头文件可以让它运行。

由于某种原因，它只显示“Q3”。我注释掉了if块内的内容，因为这给了我“信号：中止（核心转储）”错误。

4

1 回答 1

0

除了代码中的“错字”，您i在内部for循环中测试而不是j（您当前拥有的代码将永远运行该内部循环），您的函数中还有一些其他问题。

首先，该内部循环应该从 开始j = i + 1，否则当任何一个值恰好是目标的一半时将找到匹配项（在您的第二个测试用例中，它将找到匹配5 + 5项，给出4和的索引结果4）。

其次，一旦找到匹配项，该函数应该返回当前值i和j值；然后，如果外部循环在没有找到匹配项的情况下终止，我们可以返回所需的{-1, -1}信号。

这是修复了上述（和其他一些）问题的函数版本：

std::pair<int, int> findTwoSumPair(const std::vector<int>& vec, int targetSum)
{
    for (size_t i = 0; i < vec.size(); i++) {
        for (size_t j = i + 1; j < vec.size(); j++) {// Start at i + 1 and test j (not i)
            if (targetSum == vec[i] + vec[j]) {
                return{ static_cast<int>(i), static_cast<int>(j) }; // Match found
            }
        }
    }
    return { -1, -1 }; // Not found.
}
于 2021-09-02T19:09:41.393 回答