The aim is to determine whether there is a pair of items in an array whose sum equals the target value given an array arr[] of n integers. The 2Sum problem is a variant of this one.
Input: arr[] = {0, -1, 2, -3, 1}, target = -2
Output: True
Explanation: There is a pair (1, -3) with the sum equal to given target, 1 + (-3) = -2
Input: arr[] = {1, -2, 1, 0, 5}, target = 0
Output: False
There is no pair with sum equals to given target.
Table of Content
- [Naive Approach] Generating all Possible Pairs – O(n^2) time and O(1) space
- [Better Approach-1] Sorting and Binary Search – O(n*log(n)) time and O(1) space
- [Better Approach-2] Sorting and Two-Pointer Technique – O(n*log(n)) time and O(1) space
- [Best Approach] Using Hash Set – O(n) time and O(n) space
[Naive Approach] Generating all Possible Pairs – O(n^2) time and O(1) space
The very basic approach is to generate all the possible pairs and check if any of them add up to the target value. To generate all pairs, we simply run two nested loops.
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) {
int n = arr.size();
// Iterate through each element in the array
for (int i = 0; i < n; i++) {
// For each element arr[i], check every
// other element arr[j] that comes after it
for (int j = i + 1; j < n; j++) {
// Check if the sum of the current pair
// equals the target
if (arr[i] + arr[j] == target) {
return true;
}
}
}
// If no pair is found after checking
// all possibilities
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;
}C
#include <stdbool.h>
#include <stdio.h>
// Function to check whether any pair exists
// whose sum is equal to the given target value
bool twoSum(int arr[], int n, int target){
// Iterate through each element in the array
for (int i = 0; i < n; i++){
// For each element arr[i], check every
// other element arr[j] that comes after it
for (int j = i + 1; j < n; j++){
// Check if the sum of the current pair
// equals the target
if (arr[i] + arr[j] == target)
return true;
}
}
// If no pair is found after checking
// all possibilities
return false;
}
int main(){
int arr[] = {0, -1, 2, -3, 1};
int target = -2;
int n = sizeof(arr) / sizeof(arr[0]);
// Call the twoSum function and print the result
if (twoSum(arr, n, target))
printf("true\n");
else
printf("false\n");
return 0;
}Java
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){
int n = arr.length;
// Iterate through each element in the array
for (int i = 0; i < n; i++) {
// For each element arr[i], check every
// other element arr[j] that comes after it
for (int j = i + 1; j < n; j++) {
// Check if the sum of the current pair
// equals the target
if (arr[i] + arr[j] == target) {
return true;
}
}
}
// If no pair is found after checking
// all possibilities
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):
n = len(arr)
# Iterate through each element in the array
for i in range(n):
# For each element arr[i], check every
# other element arr[j] that comes after it
for j in range(i + 1, n):
# Check if the sum of the current pair
# equals the target
if arr[i] + arr[j] == target:
return True
# If no pair is found after checking
# all possibilities
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")Output
1
Time Complexity: O(n²), for using two nested loops
Auxiliary Space: O(1)