时间戳

首页 > 解决方案 > c中最大和相同的两对

algorithm - c中最大和相同的两对

问题描述

给定一个数组 a[]。找到两对 (a,b) 和 (c,d) 使得 a+b==c+d。并且 (a+b==c+d) 的和值最大为可能我们只需要打印该总和值，如果它形成具有相同总和值的两对，否则 -1

Note->NO cpp only c language allowed 这让这个问题对我来说更难

示例：N = 6, S[] = { 2, 3, 6, 4, 1, 5 } 可以选择 (6, 3) 和 (5, 4) 对，两个数可以相同，但相同的数可以不是这两对的一部分。

我的想法 1 -> 我试图让所有可能的对将对总和存储在排序数组中，然后我开始搜索表单 end 检查是否有可能找到两个具有 maxsum 的团队但无法处理类似情况 0 0 1 1 （其中包含重复）

My Thinking 2 ->all way to select 1st, 2nd and 3rd student and check if you have 4th one’s Skill 等于 (S1+S2−S3)? 然后在所有可能的团队中选择最大值。但是由于 n<=500 它将是 O(n^4) 可以给出 TLE。

请帮忙！

标签： algorithm

解决方案

让我们使用对 (a, b) 作为：

  • a：数组中数字的索引
  • b：数组中其他数字的索引（a！= b）

让我们创建一个字典 D 来存储这些对的列表。如果一对 (a, b) 满足 S[a] + S[b] = 10，则 (a, b) 应包含在列表 D[S[a] + S[b]] 中。

这意味着在 D 中找到一对的关键是原始数组中该对表示的两个元素的总和。

如果另一对 (c, d) 也满足 S[c] + S[d] = 10，则 (c, d) 将在同一个列表 D[S[a] + S[b]] 中。

我们可以遍历数组并将所有对保存在正确的列表中：

for(int i = 0; i < |S| - 1; i++){
    for(int j = i + 1; j < |S|; j++){
        D[S[i] + S[j]].Add( new pair(i, j) );
    }
}

随着你的字典被填满，你有很多对的列表，它们的总和（在原始数组中）是相同的。对于每个键 k（表示总和），询问列表 D[k] 的长度是否至少为 2，这意味着至少有 2 对持有相同的总和。如果是，请在列表中搜索没有任何共同点的两对，这将是您的答案。从最大键到最小键搜索以获得更好的性能。这种方法是 O(n²)。

推荐阅读