3Sum算法版本O（N^2 logn）时间

Question

以下算法工作：

给定n个整数NUMS和靶的阵列，找到的 索引三胞胎数I，J，K 0 < = i < j < k < n满足 条件nums [i] + nums [j] + nums [k] <目标。

例如，给定NUMS = [-2，0，1，3]，并且目标= 2

返回2.因为有两个三联体总和是小于2：

def three_sum_smaller(nums, target) 
    nums.sort! 
    i = 0 
    triplet_count = 0 
    while i < nums.length 
     j = i + 1 
     while j < nums.length 
      pair_sum = nums[i] + nums[j] 
      val = target - pair_sum 
      k = binary_search(nums, val) #if val in it, we want all indices between j and k. else all indices j and k including k. 
      (nums[k] == val) ? triplet_count += (j + 1...k).size : triplet_count += (j + 1..k).size #ensures k > j. 
      j += 1 
     end 
     i += 1 
    end 

    triplet_count    
end 

def binary_search(arr, val) 
    b_search(arr, val, 0, arr.length - 1) 
end 

def b_search(arr, val, low, high) 
    while low < high 
    mid = (low + high)/2 
    if arr[mid] > val #left half 
     high = mid - 1 
    elsif arr[mid] < val 
     low = mid + 1 
    else 
     #go left until it's no longer k and return this. 
     until arr[mid] != val 
     mid -= 1 
     end 
     return mid 
    end 
    end 

    low 
end 

我的代码是关闭的1以下的测试用例：

arr = [-3,4,-4,1,-1,-2,-1,-1,-5] 
target = -3 

Correct output: 48 
My output: 59 

该方法的工作原理如下。对于每一对可能的对，执行一个二进制搜索，查找使对==总和为目标的值。如果该值不存在，则返回小于它的索引。如果是，则返回该值的第一个匹配项。然后，如果找到该值，则仅将j和k之间的索引（不包括k）作为三元组完成。如果未找到该值，则将指标包括j作为三重完成。

这可以用于200个左右的测试用例，并且在之后失败。我不知道有什么问题..

Answer 1

的问题是在将范围添加到triplet_count之前进行相等检查。您需要如下检查>=而不是==：

def three_sum_smaller(nums, target) 
    nums.sort! 
    i = 0 
    triplet_count = 0 
    while i < nums.length 
    j = i + 1 
    while j < nums.length 
     pair_sum = nums[i] + nums[j] 
     val = target - pair_sum 
     k = binary_search(nums, val) 
     (nums[k] >= val) ? triplet_count += ((j + 1)...k).size : triplet_count += ((j + 1)..k).size 
     j += 1 
    end 
    i += 1 
    end 

    triplet_count 
end 

当您检查平等，你缺少的事实，在k位置中的数字可能会大于val所以它不是一个有效的三重。

无论如何，该溶液可以被降低到O（N^2）如果我们使用下面的想法：

我们可以固定索引（idx），然后使用两个指针（start和finish）以迭代地搜索从idx + 1到nums.length - 1的子数组找到有效范围以完成三元组。代码如下所示：

def three_sum_smaller_without_search(nums, target) 
    nums.sort! 
    triplet_count = 0 
    nums.each_with_index do |val, idx| 
    start = idx + 1 
    finish = nums.length - 1 

    while start < finish 
     if val + nums[start] + nums[finish] >= target 
     finish -= 1 
     elsif val + nums[start] + nums[finish] < target 
     triplet_count += finish - start 
     start += 1 
     end 
    end 
    end 

    triplet_count 
end 

Answer 2

愚蠢的问题：考虑到200个测试用例通过但一个失败，你确定测试输出给出的是正确的吗？

---

望着这另一种方式：（！和道歉，如果我误解）我这个算法的解释是，要找到三胞胎的总数产生的低于目标的总和。三元组不能重复使用相同的数字，但否则可以按任何顺序。

碰巧，红宝石使得超级容易从数组生成长度Ñ的组合，与combination（见https://ruby-doc.org/core-2.2.0/Array.html#method-i-combination）

利用这一点，我们可以生成所有独特三元组。然后对每一个进行求和并查看它是否符合标准是微不足道的。

因此，沿着这种思路去的替代解决方案可能是：

def solve(array, target) 
    array.combination(3).map { |p| p.reduce(&:+) }.select { |t| t < target }.count 
end 

是由于您提供的输入，这支持你的答案48：

# array: [-2, 0, 1, 3] 
# target: 2 
# => 2 

# array: [-3, 4, -4, 1, -1, -2, -1, -1, -5] 
# target: -3 
# => 48