在数组中查找和为给定值的三个数

引言

数组是编程和问题解决领域中的基本数据结构。它们使我们能够按顺序存储许多相同类型的元素。在一个数组中找到总和为特定值的三个数是许多有趣的数组相关编码问题之一。本文将研究有效解决此问题的各种策略。

理解问题

问题陈述定义

目标是给定一个整数数组和一个目标和，识别出数组中总和为指定目标值的三个元素。

朴素方法

解决此问题最简单的方法是使用三个嵌套循环。数组包含所有可行的三个数，我们可以迭代所有这些数以查看它们的总和是否与所需值匹配。尽管此方法有效，但由于其 O(n3) 的时间复杂度，对于大型数组而言效率极低。

哈希优化方法

哈希是一种我们可以用来提高效率的技术。该计划是固定一个元素，同时使用双指针方法来定位另外两个元素。数组元素的频率将被记录在哈希表中，我们将遍历数组以找到符合要求的三个数。

以下是优化方法的步骤

为了跟踪数组元素的频率，创建一个空的哈希表。

对于每次迭代，遍历数组的元素“a”

• 确定余额，和（和 = 目标和 - a）。

对数组中的每个元素“b”（但不是“a”）重复迭代过程

• 确定第三个剩余量（第三个 = 和 - b）。
• 验证“第三个”与“a”或“b”不是同一元素，并且它存在于哈希表中。
• 如果找到目标值，我们就有了一个总和为目标值的三个数 (a, b, third)。
• 就效率而言，此方法比朴素方法有效得多，时间复杂度为 O(n2)。

双指针优化方法

使用双指针技术是另一种有效的策略。此方法要求数组已排序才能起作用。

双指针方法包括以下步骤

• 对提供的数组进行非递减有序排序。
• 创建两个指针，其中“左”指针在数组开头，“右”指针在数组末尾。
• 当“左” < “右”时迭代数组
• 将“左”、“右”和最后一个“第三”元素相加得到它们的总和。
• 如果总和等于所需值，则我们找到一个三个数。
• 如果总和小于所需值，则增加“左”以探索更大的元素。
• 如果总和超过所需值，则减小“右”以探索较小的元素。
• 此方法不需要额外的空间，时间复杂度为 O(n2)，并且不是哈希方法。

最佳方法是排序

此方法的目的是在不占用额外哈希空间的情况下在数组中定位三个数。它基于排序数组然后应用双指针方法的思想。

以下是排序方法的步骤

对提供的数组进行非递减有序排序。

对于每次迭代，遍历数组的元素“a”

• 初始化“左”和“右”两个指针。“左”指向“a”后面的元素，“右”指向最后一个元素。

当“右” > “左”时

• 找到“a”、“左”和“右”元素的总和。
• 如果总和等于所需值，则我们找到一个三个数。
• 如果总和小于所需值，则增加“左”以探索更大的元素。
• 如果总和超过所需值，则减小“右”以探索较小的元素。
• 此方法的时间复杂度为 O(n2)，并且在不占用更多空间的情况下产生最佳结果。

实际应用

在数组中找到总和为特定值的三个数是许多不同领域中的常见问题。实际应用示例包括

• 财务分析的目标是找到导致特定财务结果的交易组。
• 玩视频游戏，玩家必须找到满足特定要求的组合才能完成挑战和谜题。
• 数据分析是寻找数据集中特定关系或模式的过程。

Python 代码

输出

Triplet found: [2, 3, 5]

提供的代码定义了一个名为 find_triplet 的 Python 函数，它在一个给定数组中搜索三个元素。这三个元素的总和等于指定的 target sum。如果存在满足此条件的三个数，则该函数返回该三个数；否则，它返回 None。

该函数将输入数组按升序排序，然后利用双指针高效地搜索三个数。它遍历数组，将每个元素视为一个潜在的起始点。在循环中，使用两个指针 left 和 right 来探索可以完成三个数以达到 target sum 的元素。指针根据当前总和是小于还是大于目标进行调整。