java - twoSum 算法 : How to improve this?

Question

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

Given an array of integers, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.

You may assume that each input would have exactly one solution.

Input: numbers={2, 7, 11, 15}, target=9

Output: 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

对数组进行排序。使两个指针分别指向第一个和最后一个(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) 时间，O(1) 内存