Two Sum: Как реализовано решение с комплексной сложностью O (1)?

Question

Классическая проблема с двумя суммами описана в 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) пространственные решения? Спасибо.

Answer 1

Если вас беспокоит только сложность пространства, а не временная сложность, то вам не нужно сортировать. Таким образом, вся проблема отслеживания исходных индексов уходит.

int[] twoSum(int[] numbers, int target) { 
    for (int i = 0; i < numbers.length-1; i++) { 
     for (int j = i+1; j < numbers.length; j++) { 
      if (numbers[i] + numbers[j] == target) 
       return new int[]{i+1, j+1}; 
     } 
    } 
    return null; 
} 

Если вы хотите вернуть все такие пары, а не только первый, а затем просто продолжать итерации вместо немедленно возвращаются (конечно, возвращаемый тип будет меняться в список или 2-й массив или ...).

Answer 2

Есть определенные ограничения, которых можно достичь и чего не может быть. Существуют некоторые параметры, которые зависят друг от друга. Время & Косвенные сложности - это два таких параметра, когда речь заходит об алгоритмах.

Если вы хотите оптимизировать свою проблему в космосе, это увеличит временную сложность в большинстве случаев, за исключением особых обстоятельств.

В этой проблеме, если вы не хотите увеличивать сложность пространства и хотите сохранить исходные индексы, единственный способ сделать это - не сортировать массив и принимать любые две комбинации чисел из массива и проверять если их сумма является вашей целью. Это означает, что код становится чем-то похожим на ниже.

while(i < n) 
{ 
    while(j < n) 
    { 
     if(i!=j && arr[i]+arr[j]==target) 
     { 
      int[] result = {i, j}; 
       return result; 
     } 
     j++; 
    } 
    i++; 
} 

Как вы можете видеть, это, очевидно, алгоритм O (n^2). Даже в программе, которую вы написали, сортировка будет похожей на O (nlogn).

Итак, в нижней строке, если вы хотите уменьшить сложность пространства, это увеличивает временную сложность.