数组中的三个数字总和为 O(n) 中的目标总和

Question

最近 hashedin 问了三元组和问题，其中三个数字应该加起来等于目标和。他们说要在 O(n) 中完成。

我试过在 O(n^2) 中完成。首先，我对数组进行排序，然后为了搜索组合，我必须对数组中的所有元素应用滑动 window 技术。我无法将其减少到 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

这段代码实际上returns所有可能的总和组合。但据该公司称，只需要一个三胞胎。不需要所有可能的三胞胎

Answer 1

寻找单个三元组的最佳方法是仅在 O(n^2) 中，您和面试官之间可能会有一些误解。在 O(n) 中是不可能做到的。编码愉快！

Answer 2

这是一个基于哈希的解决方案，复杂度为 O(n) Python3 程序使用散列法查找三元组，如果 A[] 中存在总和等于 'sum' 的三元组，则 returns 为真。此外，打印三元组

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

Answer 3

作为 ANSWER 提到的 python 代码本身有一个嵌套的 for 循环，因此在任何情况下，最坏情况的复杂度都是 O(n^2)。测试用例： 3 4 5 2 2 19 所需总和 = 23。这个测试用例不能在 O(n) 中解决。如果有人在 Whosebug 上回答，应该有一点责任。

Answer 4

谢谢大家的帮助。我想出了一个在 O(n) 中完成它的初始解决方案。我还不确定它是否正确，但它在所有测试用例上都是运行这里有一个Githublink下载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

下载包含测试用例的完整文件

数组中的三个数字总和为 O(n) 中的目标总和

Three numbers in an array that sum up to a target sum in O(n)

arrays

sum

triplet