Java 8 中使用 Lambda 表达式和 Stream API 解决 LeetCode 的两数之和问题
当我们在面对一个数列，需要查找其中两个元素的和为给定目标值时，可以使用两数之和（Two Sum）问题来解决。这个问题在 LeetCode 上有很高的重要性和普遍性，在各种面试中也经常会被考察。
最直接的方法是通过双重 for 循环来枚举所有可能的元素对，然后检查它们的和是否等于给定目标值。这个方法的时间复杂度是 O(n^2)，并不太适用于大型数据集。
那么如何能够更快地解决这个问题呢？我们可以使用哈希表（Hash Table）来降低时间复杂度。具体来说，我们可以建立一个从数组元素到其下标的映射，然后遍历一遍数组，对于每个元素，查找其补数是否存在于哈希表中即可。
问题
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。 你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。 你可以按任意顺序返回答案。 示例 1： 输入：nums = [2,7,11,15], target = 9 输出：[0,1] 解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。 示例 2： 输入：nums = [3,2,4], target = 6 输出：[1,2] 示例 3： 输入：nums = [3,3], target = 6 输出：[0,1] • 1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 • 16 • 17 • 18 • 19
以下是使用 Java 代码实现上述算法的标准解决方案：
public static int[] twoSum(int[] nums, int target) { for (int i = 0; i < nums.length; i++) { for (int j = i + 1; j < nums.length; j++) { if (nums[i] + nums[j] == target) { System.out.println("i的值是==》" + i + "j的值是==》" + j); System.out.println("---------------------------"); System.out.println("nums[i]的值是:" + nums[i] + "nums[j]的值是:" + nums[j] + ";target的值是=" + target); int[] result = new int[2]; result[0] = i; result[1] = j; return result; } } } return new int[0]; }
上面这段代码实现了使用双重循环来查找数组中两个元素的和等于目标值的下标。对于小型数据集，这种算法可以工作得很好，但对于大型数据集，它的时间复杂度为 O(n^2)，效率较低。
相比之下，使用哈希表算法可以把时间复杂度降低到 O(n)，提高程序的效率。这是因为哈希表可以在常量时间内完成对元素的查找操作，所以算法的总时间复杂度取决于遍历数组的时间复杂度，即线性的 O(n)。
除此之外，使用哈希表算法还具有以下优点：
可以处理包含重复元素的情况：如果输入数组中包含重复元素，那么双重循环的解法将会返回最后一组满足条件的元素下标。而哈希表算法可以正确地处理这种情况，返回第一组满足条件的元素下标。
可以处理无序数组的情况：如果输入数组是一个无序数组，那么双重循环的解法将需要进行排序操作，从而增加额外的时间和空间开销。而哈希表算法并不依赖数组的顺序，可以直接在原始数组上进行处理，减少了额外的开销。
可以处理不存在解的情况：如果输入数组中不存在满足条件的元素对，那么双重循环的解法将返回一个不正确的结果（即最后一组比较的元素对）。而哈希表算法可以检测到这种情况，并返回一个空数组。
因此，使用哈希表算法来解决两数之和问题是更加高效和可靠的方法。
以下是使用 Map代码实现上述算法的标准解决方案：
import java.util.Arrays; import java.util.HashMap; import java.util.Map; public class Solution { public static int[] t woSum(int[] nums, int target) { Map<Integer, Integer> map = new HashMap<>(); for (int i = 0; i < nums.length; i++) { int complement = target - nums[i]; if (map.containsKey(complement)) { return new int[] {map.get(complement), i}; } map.put(nums[i], i); } return new int[0]; } public static void main(String[] args) { int[] nums = {2, 7, 11, 15}; int target = 9; int[] result = twoSum(nums, target); System.out.println(Arrays.toString(result)); // 输出 [0, 1] } }
在上述代码中，我们使用了一个 Map 对象来存储数组中的元素及其下标。具体来说，在每次遍历数组中的元素时，我们检查它的补数（即目标值与当前元素之差）是否已经存在于 Map 中。如果是，那么我们已经找到了符合条件的两个元素，可以直接返回它们的下标。
如果补数不存在于 Map 中，则将当前元素及其下标添加到 Map 中，以便在查找后续元素时进行比较。
相比于双重 for 循环，这个算法的时间复杂度为 O(n)，并且空间复杂度也只需要 O(n)，因为我们需要存储数组中所有的元素和它们的下标。
除此之外，我们还可以使用 Java 8 的 Lambda 表达式和 Stream API 来简化上述算法的实现。具体来说，在使用 Lambda 表达式时，我们可以使用 IntStream.range() 方法来遍历数组元素的下标，并使用 Collectors.toMap() 方法将对应的元素和下标存储到一个 Map 对象中。然后，我们使用 filter() 方法和 findFirst() 方法来查找符合条件的元素对，并将它们转换为包含两个下标的数组。
以下是使用 Lambda 表达式实现上述算法的完整代码：
import java.util.Arrays; import java.util.Map; import java.util.stream.Collectors; import java.util.stream.IntStream; public class Solution { public static int[] twoSum(int[] nums, int target) { Map<Integer, Integer> map = IntStream.range(0, nums.length) .boxed() .collect(Collectors.toMap(i -> nums[i], i -> i)); return IntStream.range(0, nums.length) .filter(i -> map.containsKey(target - nums[i]) && map.get(target - nums[i]) != i) .mapToObj(i -> new int[] {i, map.get(target - nums[i])}) .findFirst() .orElse(new int[0]); } public static void main(String[] args) { int[] nums = {2, 7, 11, 15}; int target = 9; int[] result = twoSum(nums, target); System.out.println(Arrays.toString(result)); // 输出 [0, 1] } }
在上述代码中，我们使用了 IntStream.range() 方法来遍历数组元素的下标，并使用 Collectors.toMap() 方法将对应的元素和下标存储到一个 Map 对象中。接着，我们使用 filter() 方法和 findFirst() 方法来查找符合条件的元素对，并将它们转换为包含两个下标的数组。
需要注意的是，在最终结果数组中，下标的顺序可能与之前提供的标准解决方案中的顺序不同，但它们仍然是符合条件的元素对的下标。
代码总计
package com.example.算法; import java.util.Arrays; import java.util.HashMap; import java.util.Map; import java.util.stream.Collectors; import java.util.stream.IntStream; public class Solution { public static void main(String[] args) { int[] nums = {3, 2, 4}; int target = 6; int[] result = twoSum(nums, target); System.out.println("输出的值1=>" + Arrays.toString(result)); int[] result1 = twoSum1(nums, target); System.out.println("输出的值2=>" + Arrays.toString(result1)); int[] result2 = twoSum2(nums, target); System.out.println("输出的值3=>" + Arrays.toString(result2)); int[] result3 = twoSum3(nums, target); System.out.println("输出的值4=>" + Arrays.toString(result3)); } public static int[] twoSum(int[] nums, int target) { for (int i = 0; i < nums.length; i++) { for (int j = i + 1; j < nums.length; j++) { if (nums[i] + nums[j] == target) { System.out.println("i的值是==》" + i + "j的值是==》" + j); System.out.println("---------------------------"); System.out.println("nums[i]的值是:" + nums[i] + "nums[j]的值是:" + nums[j] + ";target的值是=" + target); int[] result = new int[2]; result[0] = i; result[1] = j; return result; } } } return new int[0]; } /** * 在这个修改后的方法中，我们首先检查目标值是否等于两个下标都是 i 的元素之和。如果是，那么我们只需在后续的循环中查找另一个满足条件的元素即可。否则，我们可以按照之前回答的代码来查找符合条件的元素对。 * <p> * 例如，在输入数组 {3, 2, 4} 和目标值 6 的情况下，下标为 0 的元素是 3，不等于目标值的一半。因此，我们直接进入第二个循环，在其中查找下标为 1 和 2 的元素之和等于目标值 6 的元素对。最终输出结果应该是 [1, 2]。 * * @param nums * @param target * @return */ public static int[] twoSum1(int[] nums, int target) { for (int i = 0; i < nums.length; i++) { if (nums[i] == target / 2) { // 特殊情况：两个下标都是 i for (int j = i + 1; j < nums.length; j++) { if (nums[j] == target / 2) { int[] result = new int[2]; result[0] = i; result[1] = j; return result; } } } else { for (int j = i + 1; j < nums.length; j++) { if (nums[i] + nums[j] == target) { int[] result = new int[2]; result[0] = i; result[1] = j; return result; } } } } // 如果没有找到符合条件的元素对，返回空数组 return new int[0]; } /** * 在这个实现中，我们使用了一个 Map 对象来存储数组中的元素及其下标。具体来说，在每次遍历数组中的元素时，我们检查它的补数（即目标值与当前元素之差）是否已经存在于 Map 中。如果是，那么我们已经找到了符合条件的两个元素，可以直接返回它们的下标。 * <p> * 如果补数不存在于 Map 中，则将当前元素及其下标添加到 Map 中，以便在查找后续元素时进行比较。 * * @param nums * @param target * @return */ public static int[] twoSum2(int[] nums, int target) { // 使用 Map 来存储数组中的元素及其下标 Map<Integer, Integer> map = new HashMap<>(); // 遍历数组中的所有元素 for (int i = 0; i < nums.length; i++) { int complement = target - nums[i]; // 检查当前元素的补数是否已经存在于 Map 中 if (map.containsKey(complement)) { // 如果已经存在，则返回它们的下标 return new int[]{map.get(complement), i}; } // 将当前元素及其下标添加到 Map 中 map.put(nums[i], i); } // 如果没有找到符合条件的元素对，则返回空数组 return new int[0]; } /** * 就是把上面的写法换成lamdba的方式 * * @param nums * @param target * @return */ public static int[] twoSum3(int[] nums, int target) { // 使用 IntStream 和 Collectors.toMap() 方法来创建 Map //IntStream.range(0, nums.length) 方法生成一个包含从 0 到 nums.length - 1 (长度-1 就是下标的值)的整数序列的 IntStream 对象。然后，boxed() 方法将这个 // IntStream 对象转换为一个装箱后的 Stream<Integer> 流。接着，Collectors.toMap() 方法将每个元素及其下标映射到一个键值对中， // 并返回一个 Map<Integer, Integer> 对象。 Map<Integer, Integer> map = IntStream.range(0, nums.length) .boxed() .collect(Collectors.toMap(i -> nums[i], i -> i)); // 使用 Stream API 来查找符合条件的元素对 //接下来，我们可以使用 filter() 方法按照是否存在符合条件的元素对进行筛选 //我们用 map.containsKey(target - nums[i]) 来判断目标值减去当前元素是否存在于 Map 中；用 map.get(target - nums[i]) != i 来判断得到的元素下标是否与当前元素下标相同，以避免重复计算。 return IntStream.range(0, nums.length) .filter(i -> map.containsKey(target - nums[i]) && map.get(target - nums[i]) != i) .mapToObj(i -> new int[]{i, map.get(target - nums[i])}) //我们可以使用 mapToObj() 方法将其转换为包含两个下标的数组 .findFirst() //最后，我们可以使用 findFirst() 方法选择第一个符合条件的元素对，并使用 orElse(new int[0]) 方法在没有找到符合条件的元素对时返回一个空数组，如下所示： .orElse(new int[0]); } }
运行结果为
总之，通过这篇博客，我们学习了如何使用哈希表求解两数之和（Two Sum）问题，并且介绍了如何使用 Java 8 的 Lambda 表达式和 Stream API 来实现这个算法。通过掌握这些技能，我们可以更加高效地解决这个问题，并在各种面试中展示出我们的编程能力。
