TwoSum 算法：如何改进？

我想做一个算法并发现这个问题leetcode http://www.leetcode.com

给定一个整数数组，找到两个数字，使它们加起来等于特定的目标数字。

函数twoSum 应返回两个数字的索引，以便它们相加达到目标，其中index1 必须小于index2。请注意，您返回的答案（索引 1 和索引 2）不是从零开始的。

您可以假设每个输入都有一个解决方案。

输入：数字={2,7,11,15}，目标=9

输出：索引 1=1，索引 2=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));
    }
}

对数组进行排序。使两个指针指向第一个和最后一个（x 和 X）。循环运行这个：

if      (a[X]+a[x] >  N) then X-- 
else if (a[X]+a[x] <  N) then x++
else if (a[X]+a[x] == N) then found.

if (x > X) then no numbers exist.

O(nlogn) time, O(1) memory