0

最近,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

此代码实际上返回所有可能的总和组合。但据该公司称,只需要一个三胞胎。不需要所有可能的三元组

4

4 回答 4

2

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

于 2019-10-07T19:16:22.037 回答
1

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

于 2019-10-07T07:47:28.153 回答
0

谢谢大家帮忙。我想出了一个在 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 上下载包含测试用例的完整文件

于 2019-10-08T06:22:18.503 回答
-1

这是一个基于散列的解决方案,复杂度为 O(n) Python3 程序使用散列查找三元组,如果 A[] 中存在总和等于“总和”的三元组,则返回 true。此外,打印三元组

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
于 2019-10-07T18:09:38.160 回答