Find two sum function in Java for Testdome

Question

I am trying to solve a problem in testdome online exam for Java.

/*
 Problem statement: Write a function that, given a list and a target sum, 
returns zero-based indices of any two distinct elements whose sum is equal to the target sum. 
If there are no such elements, the function should return null.
For example, 
findTwoSum(new int[] { 3, 1, 5, 7, 5, 9 }, 10) should return a single dimensional array with two elements and contain any of the following pairs of indices:
0 and 3 (or 3 and 0) as 3 + 7 = 10
1 and 5 (or 5 and 1) as 1 + 9 = 10
2 and 4 (or 4 and 2) as 5 + 5 = 10

 My code gives the correct output but passes 3/4 tests

 The last test case which is failing says - code takes too long to answer when array has large # of elements

 */
--here is my code--

public class TwoSum {

    public static int[] findTwoSum(int[] list, int sum) {    
        int listLength=list.length;
        int[] match=new int[2];

        for(int i=0; i<listLength; i++){
            for(int j=i+1; j<listLength; j++){
                if(list[i]+list[j]==sum){
                    match[0]=i;
                    match[1]=j;
                    return match;
                }    
            }
        }
        return null;    
    }

    public static void main(String[] args) {
        int[] indices = findTwoSum(new int[] { 1, 3, 5, 7, 9 }, 10);
        System.out.println(indices[0] + " " + indices[1]);
    }
}

Please help me to correct the code so that it can pass the 4th test case also.

you can copy paste my code in the online website and see the result.

https://www.testdome.com/d/java-interview-questions/4

Thanks in advance :)

Answer 1

Using dynamic programming with hashmap, remember to import java.util.HashMap; and import java.util.Map;

public static int[] findTwoSum(int[] list, int sum) 
{
        Map<Integer, Integer> hmap = new HashMap<>();
        for (int i=0; i<list.length; i++) 
        {
            int req = sum - list[i];
            if (hmap.get(req) != null) 
                return new int[]{i, hmap.get(req)};

            hmap.put(list[i], i);
        }

        return null;    
}