Two Sum - Elements in Array With Given Sum Java Program

In the post Two Sum - Array Indices With Given Sum Java Program we saw how to write Java program for the given problem statement to find the indices. There is another variant of two sum problem where you may be asked to find all the pairs in the array that add up to the given target. So, rather than indices of the elements in the array you need to find the numbers itself that add up to the target.

For example:

1. Input: int[] arr = {4, 7, 5, 6}, target = 10
Output: (4, 6)

2. Input: int[] arr = {4, 6, 5, -10, 8, 5, 5,20}, target = 10
Output: (-10,20) (4,6) (5,5)

3. Input: int[] arr = {18, 12, 4, 2, 1, 5, 10}, target = 6
Output: (1,5) (2,4)

Java program for this problem statement can be written using one of the following approaches.

Using nested loops which is not a very efficient solution.
Using HashSet which is more efficient.
By sorting the array and using two pointers.

1. Find pairs in an array using nested loops - Java Program

If you write the program, to find all the pair of numbers in an array that add up to the given target, using nested loops then you will have an outer loop that traverses through the array elements and an inner loop which starts from one more than the current outer loop iterator value.

public class PairsInArray {

  public static void main(String[] args) {
    int[] numArr = new int[] {4, 6, 5, -10, 8, 5, 5,20};
    int target = 10;
    findThePairs(numArr, target);
  }
  
  // With two loops 
  private static void findThePairs(int inputArray[], int target){
    String result = "";
    int len = inputArray.length;
    for(int i = 0; i < len; i++) {
      for(int j = i+1; j <len;j++) {
        int sum = inputArray[i] + inputArray[j];
        if(sum == target) {
          result = result + "(" + inputArray[i] + "," + inputArray[j] + ") ";
          break;
        }      
      }
    }
    // display all the pairs
    System.out.println(result);
  }
}

Output

(4,6) (5,5) (-10,20) (5,5)

Time and space complexity with nested loops

Since there are two loops, outer loop traversing all the elements and inner loop traversing through rest of the array to find another number to get the sum as target. Thus, the time complexity is O(n²).

Space complexity is O(1) as no auxiliary space is required with this approach.

2. Find pairs in array using HashSet - Java Program

In this approach HashSet is used to store array elements. You need to traverse array only once so only single loop is needed, in each iteration for the current element you calculate its difference with the target. Then, check in the Set to verify if there is any element already stored in the Set which is equal to this difference. If yes, that is the pair you are looking for.

public class PairsInArray {

  public static void main(String[] args) {
    int[] numArr = new int[] {4, 6, 5, -10, 8, 5, 5,20};
    int target = 10;
    findPairSet(numArr, target);
  }
  
  // Using HashSet
  public static void findPairSet(int inputArray[], int target) {
    String result = "";
    Set<Integer> pairSet = new HashSet<Integer>();
    for(int i = 0; i < inputArray.length; i++) {
      int c = target - inputArray[i];
      if(pairSet.contains(c)) {
        result = result +  "("+c + ", " + inputArray[i] + ")";
      }
      pairSet.add(inputArray[i]);
      
    }
    System.out.println(result);
  }
}

Output

(4, 6)(5, 5)(5, 5)(-10, 20)

As you can see from the output, with this approach and with nested loops you may have elements that are used more than once, extra logic is needed to take care of this. With two pointers approach you don't have this issue.

Time and space complexity with HashSet approach

Since there is only a single loop iterating the array and HashSet operations to check for value and to add elements are considered O(1) so the time complexity of this solution is O(n).

Extra space for HashSet is needed, which in worst case may store all the elements of the array so the space complexity is O(n).

3. Find pairs in array using Two pointers - Java Program

In this solution two pointer logic is used where the left pointer starts from the beginning of the array and the right pointer starts from the end of the array. Then you need to check if arr[left] + arr[right] = target, if yes you have got a pair, otherwise based on whether the sum is less than or greater than the target, you need to increment left pointer or decrement right pointer.

Array should be sorted to make it work with the two-pointer approach so that is the pre-computation required with this approach.

public class PairsInArray {

  public static void main(String[] args) {
    int[] numArr = new int[] {4, 6, 5, -10, 8, 5, 5,20};
    int target = 10;
    findPairsTwoPointer(numArr, target);
  }
  
  // With one loop - 2 pointer
  private static void findPairsTwoPointer(int inputArray[], int target){
    String result = "";
    int len = inputArray.length;
    int low = 0;
    int high = len - 1;
    // sort the array
    Arrays.sort(inputArray);
    
    while(low < high) {
      if(inputArray[low] + inputArray[high] == target){
        result = result + " (" + inputArray[low] + "," + inputArray[high] + ")";
        low++;
        high--;
            
      }else if(inputArray[low] + inputArray[high] < target){
        low++;             
      }else{
        high--;
      }
    }
    
    System.out.println(result);
  }
}

Output

(-10,20) (4,6) (5,5)

Time and space complexity with Two-pointer approach

Sorting the array is O(n log n), then traversing the loop is O(n) operation so the total time complexity is O(n log n) + O(n). Which simplifies to O(n log n).

As extra space only some variables are initialized which is not significant so the space complexity is O(1).

This is an efficient solution if array is already sorted.

That's all for this topic Two Sum - Elements in Array With Given Sum Java Program. If you have any doubt or any suggestions to make please drop a comment. Thanks!

>>>Return to Java Programs Page

Related Topics

You may also like-

Tech Tutorials

Tuesday, October 7, 2025