twoSum算法：如何改进这一点？

Question

我想做一个算法，在leetcode上发现了这个问题

给定一个整数数组，找到两个数字，使它们相加为一个特定的目标数。

函数twoSum应该返回两个数字的索引，使它们相加为目标，其中index1必须小于index2。请注意，您返回的答案(index1和index2)都不是从零开始的。

输出:index1=1,index2=2

我的解是O(n^2)。我想知道有没有更好的办法？如O(n)或O（nlogn）

import java.util.Arrays;
public class ReturnIndex {
    public int[] twoSum(int[] numbers, int target) {
        int tail = numbers.length-1;
        int[] n = new int[2];
        for (int i=0;i<tail;i++) {
            for(int j=i+1;j<tail;j++) {
                if(target ==(numbers[i]+numbers[j])) {
                    n[0] = i+1;
                    n[1] = j+1;
                }
            }
        }
        return n;
    }

    public static void main(String[] args) {
        int[] s = {150,24,79,50,88,345,3};
        int value = 200;
        ReturnIndex r = new ReturnIndex();
        int[] a = r.twoSum(s,value);
        System.out.println(Arrays.toString(a));
    }
}

Answer 1

O(n log n)时间，O(1)内存（不计算列表）：

>

首先，对列表进行排序。这需要o(n logn)时间，就像大多数排序函数一样。

遍历列表，这应该在外循环中花费O(n)时间。此时，您可以对排序子列表中最接近的匹配整数进行二分搜索，这将花费O（log n)时间。此阶段应以O(n logn)总计结束。

O(n)时间，O(n)内存：

构建一个哈希表，该哈希表应具有O(1)插入和O(1)包含。然后，在O(n)外循环中，对于每个数字i，检查total-i是否在哈希表中。如果没有，则添加；如果是，那么你就有你的两个号码了。

不管是哪种方式，您都需要对数组进行额外的扫描以获得索引，但这没有问题--这只需要O(n)时间。如果您想避免这种情况，可以根据需要将原始索引保留在排序列表或哈希表中，但这样会占用内存而不是时间占用。