开发者社区> 问答> 正文

在数组中找出三个和的总和最接近给定数字的元素

给定整数数组A 1,A 2,...,A n,包括负数和正数,以及另一个整数S。现在,我们需要在数组中找到三个不同的整数,它们的和最接近给定的整数S如果存在多个解决方案,那么任何一个都可以。

您可以假定所有整数都在int32_t范围内,并且计算总和不会发生算术溢出。S没什么特别,只是一个随机选择的数字。

除了蛮力搜索以外,还有没有其他有效的算法可以找到三个整数?

展开
收起
保持可爱mmm 2020-02-06 23:21:38 631 0
1 条回答
写回答
取消 提交回答
  • 当然,这是一个更好的解决方案,因为它更易于阅读,因此不易出错。唯一的问题是,我们需要添加几行代码,以避免对一个元素进行多次选择。

    另一个O(n ^ 2)解决方案(通过使用哈希集)。

    // K is the sum that we are looking for for i 1..n int s1 = K - A[i] for j 1..i int s2 = s1 - A[j] if (set.contains(s2)) print the numbers set.add(A[i])

    问题来源于stack overflow

    2020-02-06 23:21:57
    赞同 展开评论 打赏
问答分类:
问答地址:
问答排行榜
最热
最新

相关电子书

更多
重新定义计算的边界 立即下载
低代码开发师(初级)实战教程 立即下载
阿里巴巴DevOps 最佳实践手册 立即下载