找出列表中是否有两个元素的和等于r中的特定值

Question

这是一个典型的面试问题。给定一个列表numbers和一个特定的值k，求numbers中是否有两个元素之和等于k。如何在r中通过单遍算法而不是穷举搜索来解决这个问题?

实际操作:在r中写最优函数，接收列表numbers和特定值k，如果numbers中有两个元素求和等于k，则返回TRUE。如果没有，返回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将返回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)
)

<标题>

性能比较单位:毫秒

<表类>exprminlq是中值uqmaxnevaltbody><<tr>function1(数字,k)13.65121.27739.5822527.448540.1905277.256100function2(数字,k)5061.0885805.18610971.045167571.603013316.132547782.874100

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

让我演示一下-

• 用outer构造以x为例的数字向量的和矩阵。我们将中间结果命名为y
• 使用apply检查which元素是否等于所需的数字，例如k。我使用arr.ind参数=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，在这种情况下，输出将包含镜像，如果需要，您可以通过取一半以上的值来过滤掉镜像。

• 注意-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