Two Sum - Array Indices With Given Sum Java Program

In this post we'll see the Java program for two sum problem which states that "Given an array of integers and an integer target, return indices of the two numbers which add up to target." You return the first pair you get, if there is no pair return "No such pair exists"

For example:

1. Input: int[] arr = {4, 7, 5, 6}, target = 10
Output: [0, 3]
arr[0] + arr[3] = 4 + 6 = 10

2. Input: int[] arr = {4, 7, 5, 8}, target = 10
Output: "No such pair exists"

3. Input: int[] arr = {2, 3, 4, 1, 5}, target = 5
Output: [0, 1]

If you have to write a Java program for getting indices of the elements in the array that sum up to the given target, then you can use one of the following approaches-

Using nested loops which is not a very efficient solution.
Using HashMap which is more efficient.

Two sum problem using nested loops - Java Program

In this approach there is an outer loop that traverse through the array and an inner loop which starts from one more than the current outer loop index value.

public class TwoSum {

  public static void main(String[] args) {
    int[] arr = new int[] {4, 5, -10, 8, 6};
    int target = 10;
    int[] indicesArr = findPairsNestedLoops(arr, target);
    if(indicesArr.length == 2) {
      System.out.println("Indices are " +  indicesArr[0] + " " + indicesArr[1]);
    }else {
      System.out.println("No such pair exists");
    }
  }
  
  private static int[] findPairsNestedLoops(int[] arr, int target) {
    for(int i = 0; i < arr.length; i++) {
      for(int j = i+1; j < arr.length; j++) {
        if(arr[i] + arr[j] == target) {
          return new int[] {i, j};
        }
      }
    }
    return new int[] {};
  }
}

Output

Indices are 0 4

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. Two sum problem using HashMap - Java Program

In this approach to find indices of the two numbers which add up to target in a given array, HashMap is used to store array elements as key and its index in the array as value.

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

public class TwoSum {

  public static void main(String[] args) {
    int[] arr = new int[] {4, 5, -10, 8, 6};
    int target = 10;
    int[] indicesArr = findPairsUsingMap(arr, target);
    if(indicesArr.length == 2) {
      System.out.println("Indices are " +  indicesArr[0] + " " + indicesArr[1]);
    }else {
      System.out.println("No such pair exists");
    }
  }
  
  private static int[] findPairsUsingMap(int[] arr, int target) {
    Map<Integer, Integer> sumMap = new HashMap<>();
    for(int i = 0; i < arr.length; i++) {
      // get the differnce from the target
      int otherKey = target - arr[i];
      // check if there is any element in the Map equal to this difference
      if(sumMap.containsKey(otherKey)) {
        return new int[] {sumMap.get(otherKey), i};
      }
      sumMap.put(arr[i], i);
    }
    return new int[] {};
  }
}

Output

Indices are 0 4

Time and space complexity with HashMap solution

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

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

There is another variation of the two sum problem where rather than indices you need to find the pair of elements in the array that add up to the target. Refer this post- Two Sum - Elements in Array With Given Sum Java Program to see solution for it.

That's all for this topic Two Sum - Array Indices 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