使用映射查找总和为目标值的 int 对 [关闭]

Question

我的代码试图使用地图找到成对的

int

，其总和为目标值。但是，它仅适用于某些测试用例，不适用于其他测试用例。

输入的组织方式如下：

number_of_test_cases

然后每个测试用例如下：

number_of_values target_value
values...

示例输入 1：

2

4 9
2 7 11 13

5 1
1 -1 -1 2 2

样本输出1：

2 7
-1 2
-1 2

示例1的说明：
这里有两个测试用例。

对于第一个测试用例，有 4 个值，目标总和为 9。我们可以看到 2 和 7 的总和等于 9，并且它是唯一有效的对。

对于第二个测试用例，有两个有效对 (-1,2) 和 (-1,2)，加起来为 1。

示例输入 2：

1

4 16
2 7 11 13

输出示例2：

-1 -1

(-1, -1) 在这里用来表示不存在总和为 16 的对。

我编写了以下代码，但它只是给出第一个测试用例的结果。例如，如果输入是：

3

4 9
2 7 11 13

5 1
1 -1 -1 2 2

1 4
2

是给予

2 7 
-1 2

当它应该是

2 7
-1 2
1 2
-1 -1

这是我写的程序：

#include<bits/stdc++.h>
#include <iostream>
#include <vector>

using namespace std;

vector<pair<int,int>> twoSum(vector<int>& arr, int target, int n)
{
    // Write your code here. 
    vector<pair<int,int>> vect;
    map<int,int>mp;
    for(int i=0;i<n;i++){
        int a=target-arr[i];
        
        if((mp.empty())||(mp.count(a)==0)){
             mp[arr[i]]=1;
        }
        else{
            vect.push_back( make_pair(arr[i],a) );
            mp.erase(a);
        }
    }
    return vect;
}
#include <iostream>
#include <vector>

using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int t;
    cin>>t;
    while(t--)
    {
        int n,target;
        cin>>n>>target;
        vector<int> v(n);
        for(int i=0;i<n;i++)
        {
            cin>>v[i];
        }
        
        vector<pair<int,int>> ans=twoSum(v,target,n);
        for(auto i:ans)
        {
            if(i.first<i.second)
                cout<<i.first<<" "<<i.second<<"\n";
            else
                cout<<i.second<<" "<<i.first<<"\n";
        }
        
    }
}

Answer 1

不清楚为什么在这个问题中需要使用地图，因为您只是每次将每个条目的值设置为

1

。我建议您考虑使用

std::unordered_set

来代替：

#include <algorithm>
#include <iostream>
#include <unordered_set>
#include <vector>

struct PairSum {
  int num1;
  int num2;
};

std::vector<PairSum> twoSum(const std::vector<int> &arr, int target, int n) {
  std::vector<PairSum> result;
  std::unordered_set<int> seen;
  for (int i = 0; i < n; i++) {
    int complement = target - arr[i];
    if (seen.count(complement)) {
      auto [minVal, maxVal] = std::minmax(arr[i], complement);
      result.push_back(PairSum{.num1 = minVal, .num2 = maxVal});
    } else {
      seen.insert(arr[i]);
    }
  }
  if (result.empty()) {
    result.push_back({-1, -1});
  }
  return result;
}

int main() {
  int t;
  std::cin >> t;
  while (t--) {
    int n, target;
    std::cin >> n >> target;
    std::vector<int> v(n);
    for (int i = 0; i < n; i++) {
      std::cin >> v[i];
    }
    std::vector<PairSum> ans = twoSum(v, target, n);
    for (const auto& [num1, num2]: ans) {
      std::cout << num1 << ' ' << num2 << '\n';
    }
  }
  return 0;
}

用法示例1：

2
4 9
2 7 11 13
5 1
1 -1 -1 2 2

示例输出 1：

2 7
-1 2
-1 2

用法示例2：

1
4 16
2 7 11 13

示例输出 2：

-1 -1

用法示例3：

3
4 9
2 7 11 13
5 1
1 -1 -1 2 2
1 4
2

示例输出 3：

2 7
-1 2
-1 2
-1 -1

Answer 2

问题在于，如果有多个具有相同值的数字，您将无法处理。不要将

mp[arr[i]] = 1;

添加 1 到

arr[i]

s 的计数中。

然后在

false

分支中，从 a 的计数中

减

1，而不是使用

erase(a)

。

其他：

• 您无需将

  n

  发送至

  twoSum

  。

  arr

  有一个

  size()

  成员函数，您可以使用它来代替。在这种情况下，甚至不需要它，因为您可以简单地使用基于范围的

  for

  循环。

• 由于您没有对

  arr

  进行更改，因此请按

  const&

  进行更改。

• 至于没有匹配时返回

  {-1, -1}

  ：这是一个错误。

  -1

  可能存在于输入

  vector<int>

  中，因此这样的答案可能会被误解为匹配的

  -1

  对。如果没有匹配项，则返回空

  vector

  。

示例：

std::vector<std::pair<int, int>> twoSum(const std::vector<int>& arr, int target) {
    std::vector<std::pair<int, int>> vect;
    std::map<int, int> mp;

    for (auto val : arr) {
        int a = target - val;

        if (mp[a] == 0) { // check if we have 0 a's in store
            ++mp[val];    // dont do mp[arr[i]] = 1, add instead
        } else {
            vect.emplace_back(val, a);
            --mp[a];      // don't erase, subtract instead
        }
    }
    return vect;
}

演示

---

风格注意事项：

• 永远不要这样做：

  #include<bits/stdc++.h>

• 很少这样做：

  using namespace std;