Pair with given Sum (Two Sum)-Using Hash Set

A more effective answer to the 2Sum challenge comes from hashing. We loop traverse the items of the array storing each integer in an unordered set instead of verifying every conceivable pair. We find the complement of every number—that is, target less current number—then see whether this complement exists in the set. Should it so, we have located the pair that adds up to the target. This method greatly lowers the time complexity and enables linear time O(n) solution of the problem.

Methodically approach:

• Make an empty ordered or hash set.
• Go over the array iteratively and for every integer there:
• Find the complement—target less current number.
• Look for a complement in the set:
• Should it be, then pair found.
• Should it not be so, add the current count to the set.
• Tell them no pair exists if the loop finishes without locating one.
• The following is a code sample using the suggested method:

C++

#include <bits/stdc++.h>
using namespace std;

// Function to check whether any pair exists
// whose sum is equal to the given target value
bool twoSum(vector<int> &arr, int target){
  
    // Create an unordered_set to store the elements
    unordered_set<int> s;

    // Iterate through each element in the vector
    for (int i = 0; i < arr.size(); i++){

        // Calculate the complement that added to
        // arr[i], equals the target
        int complement = target - arr[i];

        // Check if the complement exists in the set
        if (s.find(complement) != s.end())
            return true;

        // Add the current element to the set
        s.insert(arr[i]);
    }
    // If no pair is found
    return false;
}

int main(){
    vector<int> arr = {0, -1, 2, -3, 1};
    int target = -2;

    // Call the twoSum function and print the result
    if (twoSum(arr, target))
        cout << "true";
    else
        cout << "false";

    return 0;
}

Java

import java.util.HashSet;

class GfG {

    // Function to check whether any pair exists
    // whose sum is equal to the given target value
    static boolean twoSum(int[] arr, int target){

        // Create a HashSet to store the elements
        HashSet<Integer> set = new HashSet<>();

        // Iterate through each element in the array
        for (int i = 0; i < arr.length; i++) {

            // Calculate the complement that added to
            // arr[i], equals the target
            int complement = target - arr[i];

            // Check if the complement exists in the set
            if (set.contains(complement)) {
                return true;
            }

            // Add the current element to the set
            set.add(arr[i]);
        }
        // If no pair is found
        return false;
    }

    public static void main(String[] args){

        int[] arr = { 0, -1, 2, -3, 1 };
        int target = -2;

        // Call the twoSum function and print the result
        if (twoSum(arr, target))
            System.out.println("true");
        else
            System.out.println("false");
    }
}

Python

# Function to check whether any pair exists
# whose sum is equal to the given target value
def two_sum(arr, target):
  
    # Create a set to store the elements
    s = set()

    # Iterate through each element in the array
    for num in arr:
      
        # Calculate the complement that added to
        # num, equals the target
        complement = target - num

        # Check if the complement exists in the set
        if complement in s:
            return True

        # Add the current element to the set
        s.add(num)

    # If no pair is found
    return False

arr = [0, -1, 2, -3, 1]
target = -2

# Call the two_sum function and print the result
if two_sum(arr, target):
    print("true")
else:
    print("false")

Js

// Function to check whether any pair exists
// whose sum is equal to the given target value
function twoSum(arr, target) {

    // Create a Set to store the elements
    let set = new Set();

    // Iterate through each element in the array
    for (let num of arr) {
    
        // Calculate the complement that added to
        // num, equals the target
        let complement = target - num;

        // Check if the complement exists in the set
        if (set.has(complement)) {
            return true;
        }

        // Add the current element to the set
        set.add(num);
    }
    // If no pair is found
    return false;
}

let arr = [0, -1, 2, -3, 1];
let target = -2;

// Call the twoSum function and print the result
if (twoSum(arr, target))
    console.log("true");
else 
    console.log("false");

Output

1

Time Complexity: O(n), for single iteration over the array
Auxiliary Space: O(n), for hashmap