两个加法问题 - 4 种以上的解法。
这是更新后的最新版本，解释得很清楚。请您查看一下。- https://www.ggorantala.dev/two-sum/
介绍
两数之和问题是一道经典的编程题，它被列为准备编程面试时必须解决的基础问题之一。LeetCode，这个拥有数十万活跃用户参与和解决编程问题的全球最大技术社区之一，将这道题——LeetCode两数之和问题——列为其课程中的第一道题。
让我们来讨论一下给定输入的TwoSum算法。这是编程面试中最常被问到的问题之一。
在编程面试中问过这个问题的公司包括 Facebook、亚马逊、苹果、Netflix、谷歌、微软、Adobe 以及许多其他顶尖科技公司。
问题陈述
在“两数相加”问题中，给定一个整数数组nums和一个整数，返回两个数之和等于该整数的数target。你可以假设每个输入都只有一个解，并且不能重复使用同一个元素。你可以按顺序返回答案。
示例 01：
Input: nums = [2, 7, 11, 15], target = 9
Output: [2, 7] // (because nums[0] + nums[1] == 9, we return [2, 7])
例 02：
Input: nums = [3, 2, 4], target = 6
Output: [2, 4]
例 03：
Input: nums = [3, 3], target = 6
Output: [3, 3]
思维过程
第一条路
让我们考虑数组为{3, 5, -4, 8, 11, 1, -1, 6}，和target = 10。
如果要处理唯一整数，可以使用 Java 中的 Set 接口或 Map 接口。
设X，Y在两个数字下方，题目明确指出这两个数字之和等于目标值。我们可以用数学公式表示为——
X + Y = 10 => Y = ( 10 - X )
所以，在遍历元素时，获取X值并检查(10 - X)它是否Y存在于列表中HashTable，这难道不是很容易找到吗？而且，这还是一个常量查找过程。
时间复杂度： O(n)是最坏情况，我们需要遍历所有元素。
空间复杂度为O(n)，存储元素的方式是哈希表。
第二种方法：
以上内容还有优化空间吗？
我们能否在不占用额外空间的情况下，找到更优化的解决方案？
是的，首先我们对整个数组进行排序array，然后使用两个指针来求和left。righttarget
-
排序需要时间
O(NlogN)，求和也需要时间O(n)。 -
总的来说，所需时间
O(NlogN)和空间是O(1)……
我们最后再来探讨这种双指针方法，看看有哪些解决方案。
重要提示：我们建议您仔细阅读这里展示的所有解决方案。不要直接选择最优解，虽然它们可能对您有所帮助，但并不能提升您在实际编程面试中的思维能力。
如果你想精通算法和问题解决，提高对问题及其处理方法的理解，那么你需要了解解决方案在所有可能方式中的实现方式。
解决方案
方法一：蛮力法
暴力破解法很简单，遍历每个元素 x，找到另一个等于（目标值 - x）的值。
import java.util.Arrays;
public class TwoSum {
public static void main(String[] args) {
int[] input = {2, 7, 11, 15};
int targetSum = 18;
System.out.println(Arrays.toString(twoSum(input, targetSum)));
}
public static int[] twoSum(int[] nums, int targetSum) {
for (int i = 0; i < nums.length; i++) {
for (int j = i + 1; j < nums.length; j++) {
if (nums[j] == targetSum - nums[i]) {
return new int[]{i, j};
}
}
}
throw new IllegalArgumentException("No two sum solution");
}
}
复杂性分析
时间复杂度： O(n^2)对于每个元素，我们尝试通过遍历数组的其余部分来找到它的补集，这需要 O(n) 的O(n)时间。因此，时间复杂度为 O(n) O(n^2)，其中 nn是数组中元素的长度。
空间复杂度：O(1)，因为没有使用额外的空间。
方法二：两遍哈希表
我们需要一种更高效的方法来检查数组中是否存在补集，以提高运行时间复杂度。
如果存在补集，我们需要查找它的索引。维护数组中每个元素到其索引的映射的最佳方法是什么？
我们通过牺牲空间来换取速度，从而将查找时间从 O(n) 缩短O(n)到 O O(1)(n)。为此，我们专门构建了一个哈希表，它支持在下一个常数时间内完成快速查找。
我说“接近”，是因为如果发生冲突，查找操作的复杂度可能会退化为时间复杂度。但只要哈希函数选择得当，O(n)哈希表查找操作的复杂度应该是均摊时间复杂度。O(1)
一个简单的实现方法使用了两次迭代。在第一次迭代中，我们将每个元素的值及其索引添加到表中。
然后，在第二次迭代中，我们检查(target - nums[i])表中每个元素的补集是否存在。注意，补集不能是nums[i]它本身！
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
public class TwoSum {
public static void main(String[] args) {
int[] input = {2, 7, 11, 15};
int targetSum = 18;
System.out.println(Arrays.toString(twoSum(input, targetSum)));
}
public static int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
map.put(nums[i], i);
}
for (int i = 0; i < nums.length; i++) {
int complement = target - nums[i];
if (map.containsKey(complement) && map.get(complement) != i) {
return new int[]{i, map.get(complement)};
}
}
throw new IllegalArgumentException("No two sum solution");
}
}
复杂性分析
时间复杂度： O(n)我们遍历包含 n 个元素的列表恰好两次。由于哈希表将查找时间减少到 O(n^2) O(1)，因此时间复杂度为 O(n^2) O(n)。
空间复杂度： O(n)所需的额外空间取决于哈希表中存储的项数，哈希表恰好存储n元素。
方法 03：单遍哈希表
事实证明，我们可以一次完成。在遍历并向表格中插入元素的同时，我们还会检查当前元素的互补元素是否已存在于表格中。如果存在，我们就找到了解决方案并立即返回。
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
public class TwoSum {
public static void main(String[] args) {
int[] input = {2, 7, 11, 15};
int targetSum = 18;
System.out.println(Arrays.toString(twoSum(input, targetSum)));
}
public static int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
int potentialDifference = target - nums[i];
if (map.containsKey(potentialDifference)) {
return new int[]{map.get(potentialDifference), i};
}
map.put(nums[i], i);
}
throw new IllegalArgumentException("No two sum solution");
}
}
那么，让我们看看如何使用Set界面来实现同样的功能。
import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;
public class TwoSum {
public static void main(String[] args) {
int[] input = {2, 7, 11, 15};
int targetSum = 18;
System.out.println(Arrays.toString(twoSum(input, targetSum)));
}
public static int[] twoSum(int[] array, int targetSum) {
Set<Integer> set = new HashSet<>();
for (int num : array) {
int potentialDiff = targetSum - num;
if (set.contains(potentialDiff)) {
return new int[]{potentialDiff, num};
}
set.add(num);
}
// Write your code here.
return new int[0];
}
}
复杂性分析
时间复杂度： O(n)我们遍历包含 n 个元素且每个元素只包含 1 的列表，每次在表中查找仅需 O(n^2)O(1)时间。
空间复杂度： O(n)所需的额外空间取决于表中存储的项目数量，该表最多可存储 n 个n元素。
方法 04：双指针
首先对数组进行排序，然后使用双指针 left、right 遍历数组。
import java.util.Arrays;
public class TwoSum {
public static void main(String[] args) {
int[] input = {2, 7, 11, 15};
int targetSum = 18;
System.out.println(Arrays.toString(twoSum(input, targetSum)));
}
public static int[] twoSum(int[] array, int targetSum) {
Arrays.sort(array);
int left = 0;
int right = array.length - 1;
while (left <= right) {
int s = array[left] + array[right];
if (s == targetSum) {
return new int[]{array[left], array[right]};
} else if (s < targetSum) {
left++;
} else if (s > targetSum) {
right--;
}
}
return new int[]{-1, -1};
}
}
复杂性分析
时间复杂度： O(NlogN)，排序需要O(NlogN)，循环执行需要O(n)。因此，总时间复杂度为O(NlogN)。
空间复杂度： O(1)我们没有将大量数据加载到内存中。我们使用变量来存储临时数据，这些数据是任意的。
额外内容
如果你对掌握位技巧感兴趣，我有一门课程，深受超过 10 万名程序员的喜爱。
本课程将教你如何运用位运算解决问题。位运算是一项强大的技术，可以有效提升你的算法和问题解决能力。课程内容包含简明易懂的讲解（配有草图）、详细的步骤图解，以及多种使用位运算符解决问题的方法。
这些技巧可以帮助你在竞技编程和编程面试中更快地运行算法O(1)。
这是准备 FAANG（Facebook、亚马逊、苹果、Netflix 和谷歌）公司编程面试的人最重要/最关键的主题之一。
首先，你将学习数字系统及其表示方法。然后，你将学习六种不同的位运算符：与 (AND)、或 (OR)、非 (NOT)、异或 (XOR) 和位移 (PLOR)。在整个学习过程中，你将通过大量的练习题获得实践经验，从而加深理解。
完成本课程后，你将能够更快、更高效地解决问题！🤩
我的课程链接：掌握比特操作技巧，轻松应对编程面试。
文章来源：https://dev.to/ggorantala/two-sum-problems-4c9j