给定数组 A[] 和数字 x，检查 A[] 中是否存在和为 x 的对 (也称为两数之和)

编写一个程序，给定一个包含n个数字的数组A[]和另一个数字x，检查数组A[]中是否存在两个元素的总和恰好为x。

示例

示例-1

输出

Pair with a given sum -2 is (-3, 1)
 Valid pair exists

如果我们将输出相加，1 + (-3) = -2。

示例-2

输出

No valid pair exists for 0

方法：通过计算数组本身的元素，使用简单的逻辑。

代码

给定一个数组A[]和一个数字x，在C++中检查数组A[]中是否存在总和为x的对。

输出

Pair with a given sum -2 is (-3, 1)
Valid pair exists

时间复杂度： O(n2)

辅助空间： O(1)

方法1：排序和双指针技术。

使用双指针法解决这个问题可能具有挑战性。但是，在使用双指针策略之前，需要对数组进行排序。一旦数组排序完成，就可以取两个指针，它们标记数组的开头和结尾。如果总和小于所需值，则将左指针向右移动以增加所需总和的值；如果总和大于两个元素的总和，则将右指针向左移动以减小总和。我们用一个例子来更好地理解这一点。

Give the array 1, 4, 45, 6, 10, -8, and the sum to be determined as 16.

Array is sorted after that
A = {-8, 1, 4, 6, 10, 45}

Now, increase "l" when the pair's sum is less than the necessary sum and decrease "r" when the pair's sum is more than the necessary amount.
This is due to the fact that travelling from left to right (while also sorting the array) in order to find the number that might enhance the total of a pair when the sum is smaller than the needed sum results in "l++" and vice versa.

Start with l = 0 and r = 5.
   • A[l] + A[r] (-8 + 45) > 16 resulting in r reduction Now r = 4
   • A[l] + A[r] (-8 + 10) add l. I is now equal to 1.
   • A[l] + A[r] (1 + 10) add l. At this point, l equals 2.
   • A[l] + A[r] (4 + 10) raise l, making l equal to 3.
   • A[l] + A[r] (6 + 10) == 16 => selected candidates (return 1)

注意：如果存在多个总和为给定值的对，此算法仅报告一个对。然而，它很容易为此进行修改。

算法

• hasArrayTwoCandidates (A[], ar_size, sum)
• 按非递减顺序对数组进行排序。
• 初始化两个索引变量，以在排序数组中找到候选元素。
  • 将第一个索引初始化为最左侧索引：l = 0
  • 将第二个索引初始化为最右侧索引：r = ar_size-1
• 当 l < r 时循环。
  • 如果 (A[l] + A[r] == sum) 则返回 1
  • 否则如果 (A[l] + A[r] < sum) 则 l++
  • 否则 r--
• 整个数组中没有候选元素 - 返回 0

上述策略的应用如下所示：

代码

输出

Array has two elements with given sum

复杂度分析

时间复杂度：取决于我们使用的排序算法。

如果使用归并排序或堆排序，最坏情况下为 O(n log n)。

如果使用快速排序，最坏情况下为 O(n^2)。

辅助空间：这也取决于排序算法。归并排序的辅助空间为 O(n)，堆排序的辅助空间为 O(1)。

方法2：哈希

方法：通过使用哈希方法，可以有效地解决这个问题。使用哈希映射来查看是否存在一个值“目标总和-x”，可以将其添加到当前数组值x（假设）以产生目标总和。这可以在持续时间内完成。让我们检查下一个图示。

arr[] = {0, -1, 2, -3, 1}

total = -2

Now begin your traverse:
   • '-2' is not an acceptable number for '0,' thus store '0' in the hash map in step 1.
   • Since "-1" is not a valid number, "-1" should be stored in the hash map.
   • Store "2" in hash map because the integer "-4" is not a valid value for "2".
   • Since there is no acceptable number "1" for "-3," store "-3" in hash map.
   • The answer is 1, -3 because "1" is a valid number.

算法

• 初始化一个空的哈希表 s。
• 对 A[] 中的每个元素 A[i] 执行以下操作
  • 如果 s[x - A[i]] 已设置，则打印对 (A[i], x - A[i])
  • 将 A[i] 插入 s。

伪代码

代码

输出

Pair with given sum 16 is (10,6)

复杂度分析

时间复杂度： O(n)。

因为整个数组只需要遍历一次。

辅助空间： O(n)。

已使用哈希映射来存储数组元素。

如果该对由数组中出现两次的数字组成，例如：数组 = [3,4,3]；对 = (3,3)；目标和 = 6，答案仍然有效。

方法3：使用小于x的元素的余数。

目标是求所有元素之和，这些元素在乘以x时留下从0到x-1的余数。如果x是6，则小于6且余数之和为6的数字之和是6。例如，数组包含2、4，余数2%6 = 2和4%6 = 4，它们加起来等于6。类似地，我们必须寻找余数为(1,5)、(2,4)的对。(3,3)。如果至少有一个余数为1的元素和至少一个余数为5的元素，我们无疑会得到总和为6。由于结果对的元素应小于6，我们不在此处考虑(0,6)。在(3,3)的情况下，我们必须首先确定是否存在任何余数为3的元素，之后我们才能说“存在一个总和等于x的对”。

算法

• 创建一个大小为 x 的数组。
• 将所有 rem 元素初始化为零。
• 遍历给定数组
  • 如果 arr[i] 小于 x，则执行以下操作
    • r=arr[i]%x 以获取余数。
    • rem[r]=rem[r]+1，即增加除以x时余数为r的元素计数。
• 现在，遍历 rem 数组从 1 到 x/2。
  • 如果 (rem[i] > 0 且 rem[x-i] > 0)，则打印“YES”并跳出循环。这意味着我们有一对在执行后得到 x。
• 现在，当我们在上述循环中到达 x/2 时
  • 如果 x 是偶数，为了得到一对，我们应该有两个余数为 x/2 的元素。
    • 如果 rem[x/2] > 1 则打印“YES”否则打印“NO”
  • 如果它不满足，即 x 是奇数，它将有一个单独的对，其总和为 x-x/2。
    • 如果 rem[x/2] > 1 且 rem[x-x/2] > 1，则打印“Yes”否则打印“No”；

代码

输出

Yes

复杂度分析

时间复杂度： O(n+x)。

辅助空间： O(x)。

无序映射也可以确定总和为指定值的对的索引。在这种情况下，唯一需要的修改是添加存储元素索引作为值，以及每个元素的键。

代码

输出

1 2

时间复杂度：O(n)

辅助空间： O(n)