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

Screen Shot 2020-01-02 at 17.09.26.png 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.

Screen Shot 2020-01-02 at 17.27.30.png Screen Shot 2020-01-02 at 17.28.07.png Screen Shot 2020-01-02 at 17.28.19.png Here, the sum of 10 of Target and the two elements 2 and 8 in HashSet is 10, so the loop ends and returns true.

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 Screen Shot 2020-01-02 at 17.33.37.png

Recommended Posts

Algorithm gymnastics 12
Algorithm gymnastics 10
Algorithm gymnastics 3
Algorithm gymnastics 9
Algorithm gymnastics 14
Algorithm gymnastics 2
Algorithm gymnastics 7
Algorithm Gymnastics 15
Algorithm Gymnastics 16
Algorithm gymnastics 8
Algorithm Gymnastics 17
Algorithm Gymnastics 18
Algorithm gymnastics 11
Algorithm gymnastics 5
Algorithm gymnastics 4
Algorithm Gymnastics 24 Subsets
Algorithm Gymnastics 23 Merge Intervals
Algorithm Gymnastics 20 Remove Duplicates
Algorithm Gymnastics 21 LinkedList Cycle
Algorithm Gymnastics 24 Cyclic Sort
Algorithm Gymnastics 19 No-repeat Substring
Algorithm exercise 6
Algorithm Gymnastics 24 Reverse a Linked List
Python algorithm
Algorithm exercises 13
Algorithm Gymnastics 20 Pair with Target Sum
Algorithm Gymnastics 22 Squaring a Sorted Array
Algorithm Gymnastics 24 Middle of the Linked List
Python memorandum (algorithm)
Dictionary learning algorithm
String search algorithm