找出列表中的任何两个元素是否总和为 R 中的特定值

Question

这是一道经典的面试题。给定一个列表 numbers 和一个特定值 k，找出 numbers 中的任意两个元素在求和时是否等于 k。如何在 r 中用单遍算法而不是穷举搜索来解决这个问题？

实际上：在 r 中写入最优化函数，该函数接收列表 numbers 和特定值 k，returning TRUE如果 numbers 中有两个元素相加等于 k。如果没有，return FALSE.

Answer 1

这个问题可以表述为：numbers中是否有a和b，使得： a + b = k？考虑到您已经知道 k，并假设实际上有两个数字相加后等于 k，可以假设：

a = k - b 或 b = k - a.

因此，通过 k - numbers，我们基本上可以求解上述两个方程的右侧。例如：

numbers <- c(10, 12, 6, 3) 和 k <- 9。 k - numbers 会 return c(-1, -3, 3, 6)。看到 3 和 6 是怎么出现的了吗？

要在 R 中完成所有这些，可以定义一个函数

sum_finder <- function(numbers, k) {
    diff_sequence <- k - numbers
    condition <- any(numbers %in% diff_sequence)
    return(condition)
}

或者简单地说：

sum_finder <- function(numbers, k) {
    return(any(numbers %in% (k - numbers)))
}

编辑： 出于基准测试目的，我将在这里发布到目前为止发布的解决方案和使用 microbenchmark::microbenchmark().

的性能结果

# as posted by @eduardokapp
function1 <- function(numbers, k) {
    any(numbers %in% (k - numbers))
}

# as posted by @AnilGoyal
function2 <- function(numbers, k) {
    any(apply(outer(numbers, numbers, `+`), 1, function(x){x == k}))
}

# Performance Comparison
numbers <- sample(500, 500)
k <- sample(500, 1)
microbenchmark::microbenchmark(
   function1(numbers, k),
   function2(numbers, k)
)

性能比较

单位：微秒

expr	min	lq	mean	median	uq	max	neval
function1(numbers, k)	13.651	21.277	39.58225	27.4485	40.1905	277.256	100
function2(numbers, k)	5061.088	5805.186	10971.04516	7571.6030	13316.1325	47782.874	100

Answer 2

我认为你只能在 baseR 中使用内置函数来做到这一点

我来演示一下-

使用 outer 构建数字向量的求和矩阵 say x 。我们将中间结果命名为 y
使用 apply 来检查 which 元素是否等于所需的数量，比如 k。我使用 arr.ind argument = T 以便输出再次是矩阵格式的索引。
创建一个包含 x 个值的最终矩阵，以获得所需的结果

x <- 25:40
k <- 61
y <- outer(x, x, `+`)

matrix(x[which(apply(y, 1, function(x){x == k}), arr.ind = T)], ncol = 2)

      [,1] [,2]
 [1,]   36   25
 [2,]   35   26
 [3,]   34   27
 [4,]   33   28
 [5,]   32   29
 [6,]   31   30
 [7,]   30   31
 [8,]   29   32
 [9,]   28   33
[10,]   27   34
[11,]   26   35
[12,]   25   36

我们看到有 12 个值组合满足您的条件。

注-1 对于像 sum 这样的任何交换运算，在这种情况下，输出将包含镜像，您可以通过取一半以上的值来过滤掉这些镜像，如果太想要了。
Note-2 如果你还想消除迭代自身的值，可以在进一步处理之前设置diag(y) <- 0或diag(y) <- NA

编辑鉴于修改要求，执行此操作

x <- 25:40
k <- 61

sum(outer(x, x, `+`) == k) > 0
[1] TRUE

#OR
x <- 1:6
k <- 1

sum(outer(x, x, `+`) == k) > 0
[1] FALSE

找出列表中的任何两个元素是否总和为 R 中的特定值

Find out if any two elements in a list sum to a specific value in R

logic

r

性能比较