两个和问题：给定列表的两个和问题 Python 解决方案

在本教程中，我们将使用 Python 代码来实现两数之和问题。这是数组的基本问题，您可以在 Leetcode 上找到它。我们将使用 Python 编程语言通过不同的方法来解决它。让我们理解问题陈述。

问题陈述

在此问题中，我们需要从给定的列表中找到两个元素的对，它们的和等于给定的目标值。我们可以假设数组只有一个整数对加起来等于目标和。

注意 - 给定的列表或数组必须按递增顺序排序。

示例 - 1

输出

[1, 5]

示例 - 2

输出

[2, 3]

让我们使用暴力方法解决这个问题。

方法 - 1：暴力方法

暴力方法是解决该问题的一种常用方法。在此方法中，我们的主要目标是解决问题，而不是高效地解决。我们检查每一对可能的组合，以及数组中可能的组合数量。我们将使用两个 for 循环，将两个值相加，并与目标值进行比较。如果它等于目标值，则返回整数对的索引。

算法 -

• 运行第一个循环以指向数组中解决方案的第一个索引。
• 运行另一个循环，为每个第一个整数指向解决方案的第二个索引。
• 如果两个元素都等于目标值，则返回这两个索引值

让我们使用 Python 代码来实现该算法。

两数之和问题实现

示例 -

输出

[0, 3]

解释 -

在上面的程序中，我们创建了 TwoSum 类并初始化了两个变量 list1 和 target。然后，我们声明了 solution() 方法，在该方法中，我们首先检查列表的长度并应用了两个 for 循环。第一个 for 循环用于维护第一个索引，第二个 for 循环用于维护第二个索引。我们检查两个值的总和；如果为真；我们分配了一个新列表并返回了元素的索引。

示例 - 2

输出

[1, 2]

方法 - 2：使用字典

输出

[1, 0]

解释 -

在此方法中，我们创建了 TwoSum 类，并在其中声明了 **solution()** 方法。在此方法中，我们声明了一个字典来跟踪迄今为止在值到索引中的所有值。现在，我们使用 enumerate 迭代给定的列表。然后，我们将 **num** 值从目标值中减去以搜索其对。如果找到对，则返回两个数字的索引。否则，将其添加到我们的字典中以供将来访问。

两数之和的时间复杂度（暴力方法）

我们需要使用两个 for 循环。第一个 for 循环访问 n 个元素，第二个 for 循环访问 n-1 个元素。因此，对于可能和总的对数的检查是：N*(N-1)/2，时间复杂度将是 O(N*N) = N²。

空间复杂度

0(1)：只为变量使用了恒定空间。

使用字典，只需要一个 for 循环，因此时间复杂度将是 O(N)。

方法 - 3：使用双指针

在此方法中，我们将使用二分搜索算法，其中给定的列表数组必须已排序。我们需要固定第一个索引，然后在列表中找到满足目标的必需值。

我们将使用两个指针：left 和 right；left 指示第一个元素，right 指示列表的最后一个元素。然后我们比较指针值的和与目标值的和；如果值之和等于目标值，则返回指针索引对。如果值之和大于目标值，则我们将 right 指针减一。否则，值之和小于目标值；我们需要将 left 指针增加一并检查相同的条件。

让我们理解下面的例子。

示例 -

输出

[2, 3]

使用两数之和的时间复杂度

即使在最坏的情况下，时间复杂度也将是 O(n)，因为我们只访问数组中的所有元素一次。

空间复杂度

0(1)：只为变量使用了恒定空间。

使用字典，只需要一个 for 循环，因此时间复杂度将是 O(n)。

结论

这是面试中基本且经常被问到的编程问题。在本教程中，我们介绍了解决两数之和问题的三种方法。我们建议独立实现上述方法，并练习此类问题以成功应对编码面试。