Java 8 Stream API: Efficiently iterate over arrays and solve the 'sum of two numbers' problem

This tutorial explores how to use the Java 8 Stream API combined with the Set data structure to efficiently solve the problem of finding two numbers whose sum is a specific target value in an integer list. The article will start from the traditional O(n^2) nested loop method, gradually optimize it to the Set-based O(n) iteration scheme, and finally show how to elegantly convert it into a concise and powerful Stream API implementation, including multiple forms with log output and only returning results.

When dealing with integer list data, a common need is to determine whether there are two numbers in the list whose sum is equal to a given target value. For example, given the list [1, 3, 6, 9] and the target value 8, we need to determine whether there is a situation where xy = 8.

Limitations of traditional iterative methods

The most intuitive solution is to use a nested loop to iterate over all possible pairs in the list.

 import java.util.List;

public class Main {

    static boolean validateArray(int result, List<integer> array){
        // Nested loop traverses all possible number pairs for (int i = 0; i  arrayOne = List.of(1,3,6,9);
        List<integer> arrayTwo = List.of(1,6,2,10);

        System.out.println(validateArray(8, arrayTwo)); // Output true (6 2=8)
        System.out.println(validateArray(8, arrayOne)); // Output false
    }
}</integer></integer>

The time complexity of this method is O(n^2), where n is the length of the list. This may not be a problem for smaller lists, but its performance degrades quickly when the list size increases.

Optimization algorithm: Set-based iterative method

In order to improve efficiency, we can use the Set data structure for optimization. Set's contains() method usually provides an average time complexity of O(1), which allows us to complete the search in one traversal.

The basic idea is: for each number num in the list, we calculate the difference between it and the target value result = result - num. We then check if this complement already exists in the set of numbers we previously iterated over, or if it exists in the Set representation of the entire list.

 import java.util.List;
import java.util.Set;
import java.util.HashSet;

public class Main {

    static boolean validateArrayOptimized(int result, List<integer> array){
        Set<integer> set = new HashSet(array); // Convert the list to Set to facilitate O(1) search for (Integer num : array) {
            int complement = result - num;
            // Check if the complement exists in the Set // and make sure the complement is not the current number itself to avoid the 4 4=8 situation (if there is only one 4 in the list)
            if (set.contains(complement) &amp;&amp; (result != 2 * num)) {
                System.out.printf("Found %s %s = %s%n", num, complement, result);
                return true;
            }
        }
        System.out.printf("The sum of two numbers not found is %s%n", result);
        return false;
    }

    public static void main(String[] args) {
        List<integer> arrayOne = List.of(1,3,6,9);
        List<integer> arrayTwo = List.of(1,6,2,10);
        List<integer> arrayThree = List.of(4, 2, 6); // 4 4=8, but there is only one 4 in the list

        System.out.println(validateArrayOptimized(8, arrayTwo)); // Output true (find 6 2 = 8)
        System.out.println(validateArrayOptimized(8, arrayOne)); // Output false
        System.out.println(validateArrayOptimized(8, arrayThree)); // Output false (because result != 2 * num)
    }
}</integer></integer></integer></integer></integer>

This optimized iteration method reduces the time complexity to O(n) because it only needs to traverse the list once, and each search operation is O(1). Set.copyOf(array) (Java 9) or new HashSet(array) can be used to create a Set. The result != 2 * num condition is used to ensure that we find two different numbers (or at least two complementary numbers that exist independently in the set), avoiding the situation where the target value is twice a number, but there is only one of that number in the list, and it is itself the complement.

Embracing the Java 8 Stream API

Set-based optimization methods are well suited for translation to the Java 8 Stream API. The Stream API provides a more declarative and concise way to work with collection data.

Stream API implementation (with log output)

If we need to print out the specific two numbers when a result is found, we can use a combination of filter, findFirst and map/orElseGet.

 import java.util.List;
import java.util.Set;
import java.util.HashSet;
import java.util.stream.Collectors;

public class StreamApiWithLogging {

    static boolean validateArrayWithStreamLogging(int result, List<integer> array){
        // Use Set.copyOf(array) (Java 9) or new HashSet(array)
        Set<integer> set = new HashSet(array); 

        return array.stream()
            .filter(num -&gt; {
                int complement = result - num;
                // Filter condition: The complement exists in the Set, and the target value is not equal to twice the current number return set.contains(complement) &amp;&amp; (result != 2 * num);
            })
            .findFirst() // Find the first number that meets the conditions.map(num -&gt; {
                // If found, print the log and return true
                System.out.printf("Found %s through Stream API %s = %s%n", num, result - num, result);
                return true;
            })
            .orElseGet(() -&gt; {
                // If not found, print the log and return false
                System.out.printf("The sum of two numbers not found through Stream API is %s%n", result);
                return false;
            });
    }

    public static void main(String[] args) {
        List<integer> arrayOne = List.of(1,3,6,9);
        List<integer> arrayTwo = List.of(1,6,2,10);

        validateArrayWithStreamLogging(8, arrayTwo); // Output true (find 6 2 = 8)
        validateArrayWithStreamLogging(8, arrayOne); // Output false
    }
}</integer></integer></integer></integer>

In this Stream version:

• array.stream() Converts a list to a stream.
• .filter(num -> set.contains(result - num) && (result != 2 * num)) applies filter conditions to each element in the stream. Only elements that meet the conditions can continue to flow to the next step.
• .findFirst() is a short-circuit operation that returns an Optional as soon as the first element that meets the criteria is found.
• .map(...) is executed when Optional contains a value, used to print logs and returns true.
• .orElseGet(...) is executed when Optional is empty (that is, no element that meets the conditions is found), used to print logs and return false.

Stream API implementation (only returns results)

If you only need a Boolean result to determine whether such a number pair exists, the Stream API can provide a more concise version using anyMatch.

 import java.util.List;
import java.util.Set;
import java.util.HashSet;

public class StreamApiResultOnly {

    static boolean validateArrayWithStream(int result, List<integer> array){
        Set<integer> set = new HashSet(array); // or Set.copyOf(array)

        // Use anyMatch to concisely determine whether there are elements that meet the conditions return array.stream()
                .anyMatch(num -&gt; set.contains(result - num) &amp;&amp; (result != 2 * num));
    }

    public static void main(String[] args) {
        List<integer> arrayOne = List.of(1,3,6,9);
        List<integer> arrayTwo = List.of(1,6,2,10);

        System.out.println(validateArrayWithStream(8, arrayTwo)); // Output true
        System.out.println(validateArrayWithStream(8, arrayOne)); // Output false
    }
}</integer></integer></integer></integer>

anyMatch() is a terminal operation that returns true immediately when it finds any element in the stream that matches the given predicate, otherwise it returns false after traversing the entire stream. This makes the code very concise and expressive.

Notes and Performance Considerations

1. Time complexity : Set-based methods (whether iterative or Stream API) reduce time complexity from O(n^2) to O(n). This is because the contains operation of Set is O(1) on average.
2. The role of Set : Set acts as a hash table here, providing fast search capabilities. Set.copyOf(array) (Java 9) or new HashSet(array) is used to create an immutable or mutable Set that internally removes duplicate elements from the original list.
3. * Condition `result != 2 num**: This condition is key. It ensures that the two numbers we find are not the same number. For example, if result is 8 and num is 4, then complement is also 4. Without this condition, set.contains(4) would return true, causing 4 4=8 to be considered a valid solution, even though there was only one 4 in the original list. If the requirement is to allow the same number to appear twice (that is, array.get(i) and array.get(j) can be the same index), you need to adjust the logic, such as using HashMap` to store the number and its frequency. But usually this problem refers to two numbers in "different positions".
4. Data repeatability : If the original list contains repeated numbers (such as [4, 4, 1, 7]), and the target value is 8, and we want 4 4=8 to hold, then the current Set scheme may need to be adjusted. Because Set will automatically remove duplicates, [4, 4, 1, 7] will be {1, 4, 7} after being converted into Set. When num is 4, complement is 4, result != 2 * num is false, so 4 4=8 will not be found. If 4 4=8 is allowed and there are at least two 4's in the list, more complex logic is required, such as using Map to store the number and its number of occurrences.

Summarize

The Java 8 Stream API provides a powerful and expressive way to work with collection data. Combined with appropriate data structures (such as Sets), we can optimize traditionally inefficient algorithms (such as O(n^2) nested loops) into efficient and concise O(n) solutions. Through operations such as filter, findFirst, map, orElseGet, or anyMatch, the Stream API not only makes code more readable, but also allows better utilization of multi-core processors for parallel processing in certain scenarios (although in this particular problem, the overhead of parallel streams may outweigh the benefits). Understanding the principles and applicable scenarios behind it is the key to writing high-performance and maintainable Java code.

The above is the detailed content of Java 8 Stream API: Efficiently iterate over arrays and solve the 'sum of two numbers' problem. For more information, please follow other related articles on the PHP Chinese website!