Algorithm gymnastics 10

Sum of Two Values Specify an array of integers and a value to determine if the sum of the two elements of the array is equal to the specified value.

Description

CASE1: When Target = 10, 2 + 8 = 10, so true is returned. CASE2: If Target = 20, return false because no two pairs are found.

Solution Runtime Complexity O(n) Scans the entire array once and saves the visited elements in a hash set. During the scan, for element'e'in the array, whether'val --e'exists in the hash set, That is, check if'val --e'is already accessed. If val --e is found in the hash set, then there are pairs (e, val-e) in the array and It means that the sum is equal to the specified val. Therefore, it returns true. It runs out of all the elements in the array and returns false if no such pair is found. Memory Complexity O(n) Since we use HashSet that contains the elements of the array, the memory is O (n).

Example

Let's run this algorithm with the first example, value = 10.

Implementation

findSum.java

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

public class findSum {
    public boolean find_sum_of_two(int[] A, int val) {
        Set<Integer> found_values = new HashSet<>();
        for (int a: A) {
            if (found_values.contains(val - a)) {
                return true;
            }
            found_values.add(a);
        }
        return false;
    }
}

Main.java

public class Main {

    static findSum algo = new findSum();

    static void test(int[] v, int val) {
        boolean output = algo.find_sum_of_two(v, val);
        System.out.println("exist(A, " + val + ") = " + (output ? "true" : "false") + "\n");
    }

    public static void main(String[] args) {
        int[] v = new int[]{2, 1, 8, 4, 7, 3};
        test(v, 3);
        test(v, 20);
        test(v, 1);
        test(v, 2);
        test(v, 7);
    }
}

Output