Expand Authors Top

If you have a few years of experience in the Java ecosystem and you’d like to share that with the community, have a look at our Contribution Guidelines.

November Discount Launch 2022 – Top
We’re finally running a Black Friday launch. All Courses are 30% off until next Friday:

>> GET ACCESS NOW

November Discount Launch 2022 – TEMP TOP (NPI)
We’re finally running a Black Friday launch. All Courses are 30% off until next Friday:

>> GET ACCESS NOW

Expanded Audience – Frontegg – Security (partner)
announcement - icon User management is very complex, when implemented properly. No surprise here.

Not having to roll all of that out manually, but instead integrating a mature, fully-fledged solution - yeah, that makes a lot of sense.
That's basically what Frontegg is - User Management for your application. It's focused on making your app scalable, secure and enjoyable for your users.
From signup to authentication, it supports simple scenarios all the way to complex and custom application logic.

Have a look:

>> Elegant User Management, Tailor-made for B2B SaaS

1. Overview

In this quick tutorial, we'll show how to implement an algorithm for finding all pairs of numbers in an array whose sum equals a given number. We'll focus on two approaches to the problem.

In the first approach, we'll find all such pairs regardless of uniqueness. In the second, we'll find only the unique number combinations, removing redundant pairs.

For each approach, we'll present two implementations — a traditional implementation using for loops, and a second using the Java 8 Stream API.

2. Return All Matching Pairs

We'll iterate through an array of integers, finding all pairs (i and j) that sum up to the given number (sum) using a brute-force, nested-loop approach. This algorithm will have a runtime complexity of O(n2).

For our demonstrations, we'll look for all pairs of numbers whose sum is equal to 6, using the following input array:

int[] input = { 2, 4, 3, 3 };

In this approach, our algorithm should return:

{2,4}, {4,2}, {3,3}, {3,3}

In each of the algorithms, when we find a target pair of numbers that sum up to the target number, we'll collect the pair using a utility method, addPairs(i, j).

The first way we might think to implement the solution is by using the traditional for loop:

for (int i = 0; i < input.length; i++) {
    for (int j = 0; j < input.length; j++) {
        if (j != i && (input[i] + input[j]) == sum) {
            addPairs(input[i], sum-input[i]));
        }
    }
}

This can be a bit rudimentary, so let's also write an implementation using the Java 8 Stream API.

Here, we use the method IntStream.range to generate a sequential stream of numbers. Then, we filter them for our condition: number 1 + number 2 = sum:

IntStream.range(0,  input.length)
    .forEach(i -> IntStream.range(0,  input.length)
        .filter(j -> i != j && input[i] + input[j] == sum)
        .forEach(j -> addPairs(input[i], input[j]))
);

3. Return All Unique Matching Pairs

For this example, we'll have to develop a smarter algorithm that returns only the unique number combinations, omitting redundant pairs.

To achieve this, we'll add every element to a hash map (without sorting), checking first if the pair has already been shown. If not, we'll retrieve and mark it as shown (set value field as null).

Accordingly, using the same input array as before, and a target sum of 6, our algorithm should return only the different number combinations:

{2,4}, {3,3}

If we use a traditional for loop, we'll have:

Map<Integer, Integer> pairs = new HashMap();
for (int i : input) {
    if (pairs.containsKey(i)) {
        if (pairs.get(i) != null) {            
            addPairs(i, sum-i);
        }                
        pairs.put(sum - i, null);
    } else if (!pairs.containsValue(i)) {        
        pairs.put(sum-i, i);
    }
}

Note that this implementation improves on the previous complexity, as we use only one for loop, so we'll have O(n).

Now let's solve the problem using Java 8 and the Stream API:

Map<Integer, Integer> pairs = new HashMap();
IntStream.range(0, input.length).forEach(i -> {
    if (pairs.containsKey(input[i])) {
        if (pairs.get(input[i]) != null) {
            addPairs(input[i], sum - input[i]);
        }
        pairs.put(sum - input[i], null);
    } else if (!pairs.containsValue(input[i])) {
        pairs.put(sum - input[i], input[i]);
    }
});

4. Conclusion

In this article, we explained several different ways to find all pairs that sum up a given number in Java. We saw two different solutions, each using two Java core methods.

As usual, all the code samples shown in this article can be found on GitHub — this is a Maven project, so it should be easy to compile and run it.

November Discount Launch 2022 – Bottom
We’re finally running a Black Friday launch. All Courses are 30% off until next Friday:

>> GET ACCESS NOW

Generic footer banner
2 Comments
Oldest
Newest
Inline Feedbacks
View all comments
Comments are closed on this article!