0

我正在研究 2-sum 问题，我认为我的解决方案非常有效，但是在我运行它之后，该程序显然花费了太长时间。这是我的代码：

  public int[] twoSum(int[] numbers, int target) {
        int [] original = new int[numbers.length];
        for(int i=0; i<numbers.length; i++){
            original[i] = numbers[i];
        }
        Arrays.sort(numbers);
        int [] returnArray = new int[2];
        int left = 0;
        int right = numbers.length-1;
        int found1 = 0, found2 = 0;
        int index1 = 1, index2 = numbers.length-1;
        for (;left<right;){
            if(numbers[left] + numbers[right] == target){
                found1 = numbers[left];
                found2 = numbers[right];
                break;
            }
            else if(numbers[left] + numbers[right] < target){
                left++;
            }
            else{
                right--;
            }
        }
        for(;index1<index2;){
            if(original[index1] == found1){
                returnArray[0] = index1+1;
            }
            else{
                index1 ++;
            }
            if(original[index2] == found2){
                returnArray[1] = index2+1;
            }
            else{
                index2 --;
            }

        }
        return returnArray;
    }

问题指出

您可以假设每个输入都只有一个解决方案。函数 twoSum 应该返回两个数字的索引，以便它们相加到目标，其中 index1 必须小于 index2。请注意，您返回的答案（index1 和 index2）不是从零开始的。

我的想法是首先对数组进行排序，然后找到这两个元素，然后是两个索引。而且我认为有必要先存储原始数组，因为排序会改变数组。我的解决方案的哪一部分很慢？

PS我不经常使用Java，请随时指出我的错误。

谢谢。

4

1 回答 1

0

你这里有两张通行证。一个是找到数字，另一个是记住原始索引。

如果您首先保留索引，则可以避免第二遍。

从包含按顺序索引的数组开始，即 { 1,2,3,4, ...}，然后使用非默认比较器对其进行排序：

sort(T[] a, Comparator<? super T> c)

让该比较器使用原始数组中的值对索引进行排序。

然后在索引上运行你的二和，你已经有了索引值。

于 2013-04-11T03:15:47.073 回答