如何使这段代码更有效地找到具有总和的对？

我正在做为了好玩而在 testdome.com 上进行测试，但它未能通过效率测试。还有什么更好的办法呢？我不会对任何值进行两次计数。似乎唯一的方法是通过暴力破解，这是一种 n^2 算法。

以下是问题的说明：

编写一个函数，给定一个列表和一个目标总和，返回 任意两个不同元素的从零开始的索引，其总和等于 目标总和。如果没有这样的元素，该函数应该 返回空值。

例如， findTwoSum(new int[] { 1, 3, 5, 7, 9 }, 12) 应该返回 以下任意索引元组： 1, 4 (3 + 9 = 12), 2, 3 (5 + 7 = 12), 3, 2 (7 + 5 = 12) 或 4, 1 (9 + 3 = 12)。

这是我的代码：

public class TwoSum {
public static int[] findTwoSum(int[] list, int sum) {
    if (list == null || list.length < 2) return null;
    for (int i = 0; i < list.length - 1; i++) { //lower indexed element
        for (int j = i + 1; j < list.length; j++) { //higher indexed element
            if (list[i] + list[j] == sum) {
                return new int[]{i, j};
            }
        }
    }

    //none found  
    return null;
}


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

}

编辑：这是我的最终工作代码。感谢大家！

import java.util.HashMap;
import java.util.Map;

public class TwoSum {
    public static int[] findTwoSum(int[] list, int sum) {
        if (list == null || list.length < 2) return null;
        //map values to indexes
        Map<Integer, Integer> indexMap = new HashMap<>();
        for (int i = 0; i < list.length; i++) {
            indexMap.put(list[i], i);
        }

        for (int i = 0; i < list.length; i++) {
            int needed = sum - list[i];
            if (indexMap.get(needed) != null) {
                return new int[]{i, indexMap.get(needed)};
            }
        }

        //none found
        return null;
    }

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

根据 Kon 的建议，一次性：

public static int[] findTwoSum(int[] list, int sum) {
    if (list == null || list.length < 2) return null;
    //map values to indexes
    Map<Integer, Integer> indexMap = new HashMap<>();
    for (int i = 0; i < list.length; i++) {
        int needed = sum - list[i];
        if (indexMap.get(needed) != null) {
            return new int[]{i, indexMap.get(needed)};
        }

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

    //none found
    return null;
}

看看你在内部循环中做了什么，检查是否 list[i] + list[j] == sum。

如果你稍微改变方程，这意味着给定 list[i] 和 sum （它们都是内部循环中的常量），你实际上是在问“是否有一个存储值 (sum - list[i]) 的索引” ，这就是你的内循环解决的问题。

现在应用您可以在线性时间内使用 indexOf(sum - list[i]) 式方法来解决问题的知识，有一些数据结构可以比 O(N) 更快地回答此类问题。