找到数组中两个元素的索引，使它们的和等于目标值。

Question

我希望通过使用流的方式，在数组中添加整数，直到达到目标和，然后返回加起来等于目标和的索引。请注意保留html标签。

例如，如果提供的数组是{1, 2, 3, 4}，并且target是4，则该方法应该打印出一个由索引{0,2}组成的int数组，但实际上并没有打印出。以下是代码：

public static int[] twoSum(int[] numbers, int target) {
    IntStream.of(0, numbers.length - 1).boxed()
            .flatMap(i -> IntStream.range(i , numbers.length - 1).boxed()
            .filter(j -> numbers[j] + numbers[i] == target)
            .flatMap(j -> Stream.of(new int[]{i , j}, new int[] {j,i})))
            .forEach(num -> System.out.println(Arrays.toString(num)));

    return numbers;
}

public static void main(String[] args) {
    System.out.println(Arrays.toString(twoSum(new int[]{1,2,5,1}, 4)));
}

- bdunaway

---

如果不添加.boxed()，则int[] b = Arrays.stream(numbers).filter((x -> num[finalI] + x == 4)).toArray();。此外，这不应该是== target吗？ - Elliott Frisch

是的，它应该是目标，我只是暂时硬编码了目标，但我也将其更改为int[] b = Arrays.stream(numbers).filter((x -> num[finalI] + x == 4)).toArray(); 这个方法有效。但是由于某种原因，它返回一个空数组。 - bdunaway

请提供源数组和期望结果的示例。例如，对于数组 1, 4, 3, 0, 4, 1 和目标总和 4，应该得到什么结果？ - Alexander Ivanchenko

如果目标和为4，则它将返回索引0和索引2，因为这些元素的总和为4。 - bdunaway

我在考虑创建一个Instream.range(0, number.length-1).boxed，它可以作为初始循环，然后创建另一个instream，将所有索引与初始的boxed流进行比较。 - bdunaway

Answer 1

首先，让我们描述解决问题的可能方法：

- 暴力方法：使用嵌套循环或使用嵌套流（提醒：流只是迭代的一种方式）迭代源数组，并检查每个元素是否有与之对应的数组元素，以便它们共同构成给定的总和。时间复杂度为O(n^2)。 - 所谓的双指针方法：对给定的数组进行排序，定义两个变量，最初指向第一个和最后一个索引，然后移动指针。此算法只能使用命令式样式实现。时间复杂度为O(n log n)（因为需要排序），比嵌套循环/流要好得多。 - 创建一个Map，将存储所有导致目标总和的元素对。该算法在线性时间O(n)内运行。只需要对源数组进行两次迭代。

下面的解决方案提供了一种利用Map的基于流的实现方法。

作为第一步，我们需要生成一个Map，它将关联一个值，该值需要添加到特定元素中，以便获得目标总和（一个键），以及数组元素的索引（一个值）。

然后，在给定数组的索引上创建一个流，过滤出与Map中的键匹配的第一个元素，并基于它构造一个双值数组。

如果未找到结果，则返回一个空数组。

public static int[] twoSum(int[] numbers, int target) {
    Map<Integer, Integer> sumMap = getSumMap(numbers, target);
    
    return IntStream.range(0, numbers.length)
        .filter(i -> sumMap.containsKey(numbers[i]))
        .mapToObj(i -> new int[]{i, sumMap.get(numbers[i])})
        .findFirst()
        .orElse(new int[0]);
}

public static Map<Integer, Integer> getSumMap(int[] numbers, int target) {
    rreturn IntStream.range(0, numbers.length)
        .boxed()
        .collect(Collectors.toMap(
            i -> target - numbers[i], //  a key - dif between target sum and a current element
            Function.identity(),      //  a value - index of the current element
            (left, right) -> left));  //  resolving duplicates
}

main() - 示范

public static void main(String[] args) {
    System.out.println(Arrays.toString(twoSum(new int[]{1, 4, 3, 0, 4, 1}, 4)));
}

输出

[0, 2] // indices of the first pair of elements (1, 3) that can produce the sum of `4`

- Alexander Ivanchenko

---

你能解释一下在getsummap中Function.identity()的作用是什么吗？ - bdunaway

@bdunaway identity() 返回传递的输入参数，不做任何修改。它与以下lambda表达式 i -> i 的意思相同。通常使用Function.identity()是一种常见的做法。 - Alexander Ivanchenko

Answer 2

你可以嵌套两个IntStreams来产生所需的结果（据我理解，这是替代使用for循环的方法）。这将返回所有总和为目标值的对。这不包括数组中相加等于目标值的元素。因此，对于目标值为4，[2, 2]不作为结果包含在内。

int[] arr1 = { 1, 2, 3, 4, 5, -2, -1, -3, -4, -5 };

int[][] array = twoSum(arr1, 4);

for (int[] a : array) {
    System.out.println(Arrays.toString(a));
}

打印

[1, 3]
[5, -1]

• 首先，从0到数组大小减1的范围内流式传输一系列整数。
• 然后使用boxed将int转换为对象。
• 然后您可以使用flatMap（将嵌套流合并为一个）另一个IntStream，该流从前一个流开始，但长度为数组的完整长度加1。
• 仍在flatMap结构内，并使用IntStreams的值作为提供的数组的索引，过滤掉不加到目标的值，并创建两个数字的数组，这些数字确实相加（如果需要，这也可以替换为数组的索引）。
• 然后将此数组的数组作为结果返回。

public static int[][] twoSum(int[] numbers, int target) {
    return IntStream.range(0, numbers.length - 1)
            .boxed()
            .flatMap(i -> IntStream.range(i + 1, numbers.length)
                    .filter(k -> numbers[i] + numbers[k] == target)
                    .mapToObj(k -> new int[] { numbers[i],numbers[k] }))
            .toArray(int[][]::new);
}

- WJS

Answer 3

不确定，但如果您正在完全使用此代码，则可能是因为foreach后面的拼写错误。您将输入初始化为nu，但将其打印为num。

.forEach(num -> System.out.println(Arrays.toString(num)));

也许用你所拥有的替换它可以解决这个问题。

编辑

针对评论的更多澄清，我们意识到问题出在给定的值上，与Java流API无关。

- Ebi