Три числа в массиве, которые суммируют до целевой суммы в O (n)

Question

Недавно hashedin задал проблему триплетной суммы, где три числа должны складываться до целевой суммы. Они сказали сделать это в O (n).

Я пытался сделать это в O (n ^ 2). Сначала я отсортировал массив, а затем для поиска комбинации мне пришлось применить технику скользящего окна ко всем элементам массива. Я не могу уменьшить его до O (n).

def threeNumberSum(array, targetSum):
    array.sort()
    l = len(array)
    trip = list()
    for i in range(l-2):
        left = i+1
        right = len(array)-1
        while left<right:
            currentSum = array[i] + array[left] + array[right]
            if currentSum == targetSum:
                trip.append([array[i], array[left], array[right]])
                left += 1
                right -= 1
            elif currentSum < targetSum:
                left += 1
            else:
                right -= 1
    return trip

Этот код фактически возвращает все возможные комбинации сумм. Но, по словам компании, нужен только один триплет. Все возможные триплеты не нужны

Answer 1

Код Python, упомянутый как ANSWER, имеет вложенный цикл for, следовательно, в любом случае сложность в худшем случае будет O (n ^ 2). Контрольный пример: 3 4 5 2 2 19 Требуемая сумма = 23. Этот контрольный пример не может быть решен в O (n). Должна быть небольшая ответственность, если кто-то отвечает на stackoverflow.

Answer 2

Наилучший из возможных подходов к нахождению одного триплета - только в O (n ^ 2), между вами и интервьюером могут возникнуть некоторые недоразумения. Это невозможно сделать за O (n). Удачного кодирования!

Answer 3

Спасибо всем за попытку помочь. Я пришел с первоначальным решением, чтобы сделать это в O (N). Я еще не уверен, что это правильно, но он работает на всех тестовых примерах. Вот ссылка на Github для загрузки файла python github.com / TripletInArrayWithTargetSum

def trip(arr, target):
    d = dict()
    n = len(arr)
    for i in arr:
        d[i] = 1

    i = 0
    j = n - 1
    while i<j:
        s = arr[i] + arr[j]     # Calculate the sum of the elements at i and j position
        diff = target - s       # Calculate the difference needed to complete the table
        if arr[i] != diff and arr[j] != diff and diff in d: # Check if the difference exists in the hashtable and as we cannot reuse elements
            return [arr[i], arr[j], diff]                   # diff should not be equal to elements at i or j and  then return the triplet if exists
        else:
            if s > target:                                  # If difference dosent exists then we adjust pointers
                j -= 1
            elif s == target:
                if arr[i+1] + arr[j] < target:
                    i+=1
                else:
                    j-=1
            else:
                i += 1

    return [None]

Загрузить полный файлс тестами на Github

Answer 4

Это решение, основанное на хешировании, которое имеет сложность O (n). Программа Python3 для нахождения триплета с использованием хеширования возвращает true, если в A [] есть триплет с суммой, равной 'sum'. Также печатает тройку

def find3Numbers(A, arr_size, sum): 
  for i in range(0, arr_size-1): 
      # Find pair in subarray A[i + 1..n-1]  
      # with sum equal to sum - A[i] 
      s = set() 
      curr_sum = sum - A[i] 
      for j in range(i + 1, arr_size): 
          if (curr_sum - A[j]) in s: 
              print("Triplet is", A[i],  
                      ", ", A[j], ", ", curr_sum-A[j]) 
              return True
          s.add(A[j])  
  return False