在 Java 中为 Testdome 找到两个求和函数

Question

我正在尝试解决 Java 的 testdome 在线考试中的问题。

/*
 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]);
    }
}

请帮我改正代码，让它也能通过第4个测试用例。

你可以在在线网站上复制粘贴我的代码并查看结果。

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

提前致谢:)

Answer 1

使用hashmap动态规划，记得import java.util.HashMap;和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;    
}

在 Java 中为 Testdome 找到两个求和函数

Find two sum function in Java for Testdome

java

rpa