java - 在 Java 中计算与目标总和对应的数组索引的代码优化空间是否存在？

Question

这是我的代码，用于获取其值的总和对应于给定目标值的数组的索引。目前在最坏的情况下是 O(N2) 算法。有什么改进方法吗？

public class SumArrayTarget {

public static void main(String[] args) {
        int[] arr = { 1, 2, 4, 6, 3, 5, 7 };
        System.out.println("The indices are "+ Arrays.toString(sum(arr, 12)));
    }

    public static int[] sum(int[] arr, int target) {
        int[] list = new int[2];
        for (int i = 0; i < arr.length - 1; i++) {
            int j = i+1;
            while (j < arr.length) {
                if (arr[i] + arr[j++] == target){
                    list[0]=i;
                    list[1]=j-1;
                    return list;
                }
            }
        }
        return list;
    }
}

Answer 1

您的算法假设总有两个数字加起来达到所需的目标。如果没有，则返回一个空的索引列表 {0,0}。如果这是您需要的行为，那么我可以想到一种复杂性改进:

• 将您的输入数组放入 LinkedHashMap，将数字映射为键，将其索引映射为值。花费 O(n) 时间。
• 遍历 map 。对于具有键 n 的每个项目:
• • 查看 map 中是否存在具有键 target - n 的元素，如果存在，则返回一个包含两个键的数组。每个元素花费预期的 O(1) 时间。
• 如果 map 的所有元素都没有相应的答案，则返回 null 或其他内容以指示没有可能的答案。

这使算法的总运行时间达到了预期的 O(n)，但开销非常大。对于小于一百万的输入数组，您的蛮力方法可能更好。

如果您尝试回答的问题也允许两个以上的索引作为结果，那么您就遇到了整数背包问题。你可以谷歌一下，但它会变得更加复杂!

编辑:添加示例实现。

public static int[] sum(int[] arr,int target) {
    LinkedHashMap<Integer,Integer> map = new LinkedHashMap<Integer>(arr.length);
    for(i = 0;i < arr.length;i++) {
        map.add(arr[i],i);
    }
    for(Map.Entry<Integer,Integer> entry : map.entrySet()) {
        int n = entry.getValue();
        int index = entry.getKey();
        if(map.containsKey(target - n)) {
            return new int[] {index,map.get(target - n)};
        }
    }
    return null;
}