Две суммы: как реализуется решение с пространственной сложностью O(1)? ⇐ JAVA

[Anonymous]

Классическая проблема двух сумм описана в LeetCode.

Я знаю, как решить ее с помощью хеш-таблицы, что приводит к дополнительному пространству O(n). Теперь я хочу решить эту проблему с помощью пространства O(1), поэтому сначала отсортирую массив, а затем использую два указателя, чтобы найти два целых числа, как показано в (неправильном) коде ниже.

Код: Выделить всё

public int[] twoSum(int[] numbers, int target) {
java.util.Arrays.sort(numbers);
int start = 0, end = numbers.length - 1;
while(start < end) {
if(numbers[start] + numbers[end] < target) {
start++;
}
else if(numbers[start] + numbers[end] > target) {
end--;
}
else {
int[] result = {start + 1, end + 1};
return result;
}
}
return null;
}

Этот код неверен: я возвращаю индексы после сортировки. Так как же мне отслеживать исходные индексы выбранных целых чисел? Или существуют другие пространственные решения O (1)? Спасибо.