在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

>

是的，我将从排序数组开始。

但在那之后，我将只使用二叉树来查找第一个（现在是当前）元素的对。

即使当前元素没有正确的对，我也会记得我寻找它的地方。

对于下一个元素，我将从记忆中的位置向后寻找对。

返回到2，直到被查找对的索引满足。

Answer 2

对于一个非常大的数组arr，可以通过对数组进行排序（即O（N logn）），使其成为O（N logn），然后对每个元素arr[i]，对数组的其余部分arr[i 1]进行二进制搜索（不是最好的，请参见下文），直到最后一个查找target-arr[i]的元素。二进制搜索是O（logn），所以整个算法是O（nlogn）。这需要一个相当大的N才能使它有价值——比7大得多。

您可以在当前代码中节省一点时间：（1）如果在开始内部循环之前计算x=target-arr[i]，并在内部循环中选中arr[j]==x。（2） 如果你知道问题的一个条件是arr的所有元素都是正的，那么在你像上面那样计算x之后，如果x，你可以完全跳过内部循环

附言：如果找不到结果，请确保您知道要返回什么。您当前的代码将返回一个2元素数组，其中两个元素都是0。这可能没关系，因为调用者可以检查这一点，但是最好返回null，特别是因为0是在其中一个元素中返回的有效值。

PPS。再考虑一下，一旦你对数组进行了排序，你就不需要进行二进制搜索来得到答案；你应该能够在O（N）时间内完成，让一个索引在数组中前进，另一个索引在数组中后退。此外，当你排序时，你可能想要创建一些小对象，其中包括arr中的值和原始索引，并对它们进行排序，这样你就可以把原始索引放在返回数组中。或者只需搜索arr中找到的两个值，即O（N）。

Answer 3

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

• 将输入数组放入LinkedHashMap，将数字映射为键，将其索引映射为值。花了很多时间

这使得算法的总运行时间达到预期的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;
}