查找数组中一对元素的索引，使它们加起来等于目标值

Question

我想通过添加整数直到达到数组中的 target 求和，然后 return indexes 加起来等于目标通过使用流。

例如，如果提供的数组是{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)));
}

Answer 1

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

Brute-force方法：使用嵌套循环或使用嵌套流迭代源数组（提醒：stream 只是迭代的平均值) 并检查数组中的每个元素是否有对应的 for，以便它们一起构成给定的总和。时间复杂度为 O(n^2).
So-called two-pointer 方法：对给定的数组进行排序，定义两个变量初始指向第一个和最后一个索引，然后移动指针。该算法只能使用命令式实现。时间复杂度为O(n log n)（因为需要排序），嵌套loop/streams.
创建一个 Map 将所有结果对存储到目标总和中。该算法在线性时间 O(n) 内运行。只需要对源数组进行两次迭代。

下面的解决方案提供了 stream-based 方法的实现，该方法利用 Map。

作为第一步，我们需要生成一个 map，它将关联一个需要添加到特定元素以获得 target 的值求和 (a key) 和数组元素的索引 (a value).

然后在给定数组的索引上创建一个流，过滤掉 map 中与 key 匹配的第一个元素，然后以此为基础构建two-value数组

如果未找到结果 - return 一个空数组。

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`

Answer 2

不确定，但如果您确实在使用这段代码，可能是因为您在 foreach 之后有拼写错误。您将输入作为 nu 启动，但将其打印为 num.

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

也许用你现有的替换它就可以解决问题。

编辑

关于评论的更多说明，人们意识到这是给定值的问题，与 Java 流 API.

无关

Answer 3

您可以嵌套两个 IntStreams 而不是使用 for 循环来产生所需的结果（据我所知）。这将 return 所有总和为目标值的对。这不包括添加到自身等于目标的数组元素。因此，对于 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 从比前一个流多一个开始，但是数组的全长。
仍在 flatMap 构造中，并使用 IntStreams 的值作为提供数组的索引，过滤掉不与目标求和的值，并创建一个数组两个相加的数字（如果需要，也可以用数组的索引替换）。
然后return这个数组数组作为结果

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);
}

查找数组中一对元素的索引，使它们加起来等于目标值

Find Indices of the pair of elements in the Array such that they add up to the Target value

java

arrays

algorithm

java-stream