找到两个相关索引，其中两个元素等于目标值

Question

背景：

给出了一个整数数组，将两个数字的返回索引加起来为特定的目标。

您可以假设每个输入完全具有一个解决方案，并且您可能不会两次使用相同的元素。

示例：

给定的nums = [2，7，11，15]，目标= 9，

因为nums [0] nums [1] = 2 7 = 9，

返回[0，1]。

问题：

我有一个数字1,2,3,4,5的列表。我的目标值是8，因此我应该返回索引2和4。我的第一个想法是为循环编写一个双重循环，以查看添加列表中的两个元素是否会获得我的目标值。虽然，在检查是否有这样的解决方案时，我的代码返回没有。

这是我的代码：

#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> list;
    list.push_back(1);
    list.push_back(2);
    list.push_back(3);
    list.push_back(4);
    list.push_back(5);
    int target = 8;

    string result;
    for(int i = 0; i < list.size(); i++) {
        for(int j = i+1; j < list.size(); j++) {
            if(list[i] + list[j] == target) {
                result = "There is a solution";
            }
            else {
                result = "There is no solution";
            }
        }
    }
    cout << result << endl;

    return 0;
}

也许我的方法/思维是完全错误的。谁能提供解决此问题的任何提示或建议？

Answer 1

您的方法是正确的，但您忘记了自己在找到解决方案后继续进行的循环。

这将使您到达中途。我建议将两个循环放入功能中，并在找到匹配项后返回。您可以做的一件事是从该功能返回pair<int,int>，或者您可以简单地从循环中的该点输出结果。

bool solutionFound = false;
int i,j;
for(i = 0; i < list.size(); i++) 
{
    for(j = i+1; j < list.size(); j++) 
    {
        if(list[i] + list[j] == target) 
        {
            solutionFound = true;
        }
    }
}

这是函数方法的外观：

pair<int, int> findSolution(vector<int> list, int target)
{
  for (int i = 0; i < list.size(); i++)
  {
    for (int j = i + 1; j < list.size(); j++)
    {
      if (list[i] + list[j] == target)
      {
        return pair<int, int>(i, j);
      }
    }
  }
  return pair<int, int>(-1, -1);
}
int main() {
  vector<int> list;
  list.push_back(1);
  list.push_back(2);
  list.push_back(3);
  list.push_back(4);
  list.push_back(5);
  int target = 8;
  pair<int, int> results = findSolution(list, target);
  cout << results.first << " " << results.second << "n";
  return 0;
}

这是C 结合了Dave的线性执行时间的答案，并有一些有用的评论：

pair<int, int> findSolution(vector<int> list, int target)
{
  unordered_map<int, int> valueToIndex;
  for (int i = 0; i < list.size(); i++)
  {
    int needed = target - list[i];
    auto it = valueToIndex.find(needed);
    if (it != valueToIndex.end())
    {
      return pair<int, int>(it->second, i);
    }
    valueToIndex.emplace(list[i], i);
  }
  return pair<int, int>(-1, -1);
}
int main() 
{
  vector<int> list = { 1,2,3,4,5 };
  int target = 10;
  pair<int, int> results = findSolution(list, target);
  cout << results.first << " " << results.second << "n";
}

Answer 2

您在n^2时间中这样做。通过哈哈每个元素进行线性时间来解决它，并检查每个元素以查看是否是补充WRT。您要实现的总数是在哈希中。

，例如，1,2,3,4,5，目标为8

indx 0, val 1: 7 isn't in the map; H[1] = 0
indx 1, val 2: 6 isn't in the map, H[2] = 1
indx 2, val 3: 5 isn't in the map, H[3] = 2
indx 3, val 4: 4 isn't in the map, H[4] = 3
indx 4, val 5: 3 is in the map. H[3] = 2. Return 2,4

代码，按要求（Ruby）

def get_indices(arr, target)
    value_to_index = {}
    arr.each_with_index do |val, index|
        if value_to_index.has_key?(target - val)
            return [value_to_index[target - val], index] 
        end
        value_to_index[val] = index
    end
end
get_indices([1,2,3,4,5], 8)

Answer 3

基本上与zzxyz的最新编辑相同，但更快，更脏。

#include <iostream>
#include <vector>
bool FindSolution(const std::vector<int> &list, // const reference. Less copying
                  int target)
{
    for (int i: list) // Range-based for (added in C++11)
    {
        for (int j: list)
        {
            if (i + j == target) // i and j are the numbers from the vector. 
                                 // no need for indexing
            {
                return true;
            }
        }
    }
    return false;
}
int main()
{
    std::vector<int> list{1,2,3,4,5}; // Uniform initialization Added in C++11. 
                                      // No need for push-backs of fixed data
    if (FindSolution(list, 8))
    {
        std::cout << "There is a solutionn";
    }
    else
    {
        std::cout << "There is no solutionn";
    }
    return 0;
}