假设您有一个已排序 vector {xi}i=1n，其元素都是正数并且不包含任何关系(=此 vector 中没有两个元素相同)。
我正在寻找最聪明的方法来检查:
2xi - xj - xk != 0 对于所有 1 <= i="" !="j" !="k"><= n="">
我有一种预感，这可以在时间 O(nlog n) 内完成，或者在比原始时间更好的情况下完成，也许使用类似于 this question 的答案中开发的策略。 .
回想一下，x 的条目都是正数且已排序，因此 x_k+k_j 的条目也已排序。
附言我正在寻找与算法/语言无关的想法。 c++标签主要在那里 如果这样做需要利用一些智能缓存策略。
@liori 在下面提出了一个很好的观点，即找到给定 i 的对 (j,k) 是 O(n)，使用类似于所做的算法 in the last iteration of this answer to a related question .这里的问题是 IMO 是否有可能比天真地更有效地组合这些 O(n) 步骤。例如，我们可以在时间 O(n) 内找到给定索引 i 的 (j,k) 对。但是我们是否需要再次考虑 all 条目 j'<=j 并且=""><=k 作为以下索引="" i'="i+1">
最佳答案
请注意，“已排序”对您没有帮助，因为基于比较的排序可以在 O(n log n) 时间内对任何包含 n 个数字的列表进行排序。
我不能完全证明3SUM - completeness对于这个问题，但是this paper by Jeff Erickson证明，在受限的计算模型中，不存在针对您的问题的次二次算法。这不是完全不可能的证明，但埃里克森使用的计算模型允许我能想到的所有合理技巧。特别是，我怀疑此站点上的任何人是否会在不久的将来针对您的问题提出 O(n log n) 算法。
您可能会感兴趣，在某些允许有限并行的计算模型中，存在 3SUM 的次二次算法。我相信this paper by Baran, Demaine, and Patrascu是第一个展示这一点的人。
关于C++ 在 O(nlog(n)) 时间内检查这个条件？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/25877101/
为了将Cucumber用于命令行脚本，我按照提供的说明安装了arubagem。它在我的Gemfile中，我可以验证是否安装了正确的版本并且我已经包含了require'aruba/cucumber'在'features/env.rb'中为了确保它能正常工作，我写了以下场景:@announceScenario:Testingcucumber/arubaGivenablankslateThentheoutputfrom"ls-la"shouldcontain"drw"假设事情应该失败。它确实失败了，但失败的原因是错误的:@announceScenario:Testingcucumber/ar
我的瘦服务器配置了nginx，我的ROR应用程序正在它们上运行。在我发布代码更新时运行thinrestart会给我的应用程序带来一些停机时间。我试图弄清楚如何优雅地重启正在运行的Thin实例，但找不到好的解决方案。有没有人能做到这一点？ 最佳答案 #Restartjustthethinserverdescribedbythatconfigsudothin-C/etc/thin/mysite.ymlrestartNginx将继续运行并代理请求。如果您将Nginx设置为使用多个上游服务器，例如server{listen80;server
这个问题在这里已经有了答案:Checktoseeifanarrayisalreadysorted?(8个答案)关闭9年前。我只是想知道是否有办法检查数组是否在增加？这是我的解决方案，但我正在寻找更漂亮的方法:n=-1@arr.flatten.each{|e|returnfalseife
我不确定传递给方法的对象的类型是否正确。我可能会将一个字符串传递给一个只能处理整数的函数。某种运行时保证怎么样？我看不到比以下更好的选择:defsomeFixNumMangler(input)raise"wrongtype:integerrequired"unlessinput.class==FixNumother_stuffend有更好的选择吗？ 最佳答案 使用Kernel#Integer在使用之前转换输入的方法。当无法以任何合理的方式将输入转换为整数时，它将引发ArgumentError。defmy_method(number)
我有一个用户工厂。我希望默认情况下确认用户。但是鉴于unconfirmed特征，我不希望它们被确认。虽然我有一个基于实现细节而不是抽象的工作实现，但我想知道如何正确地做到这一点。factory:userdoafter(:create)do|user,evaluator|#unwantedimplementationdetailshereunlessFactoryGirl.factories[:user].defined_traits.map(&:name).include?(:unconfirmed)user.confirm!endendtrait:unconfirmeddoenden
我有一个包含多个键的散列和一个字符串，该字符串不包含散列中的任何键或包含一个键。h={"k1"=>"v1","k2"=>"v2","k3"=>"v3"}s="thisisanexamplestringthatmightoccurwithakeysomewhereinthestringk1(withspecialcharacterslike(^&*$#@!^&&*))"检查s是否包含h中的任何键的最佳方法是什么，如果包含，则返回它包含的键的值？例如，对于上面的h和s的例子，输出应该是v1。编辑:只有字符串是用户定义的。哈希将始终相同。 最佳答案
我需要检查DateTime是否采用有效的ISO8601格式。喜欢:#iso8601?我检查了ruby是否有特定方法，但没有找到。目前我正在使用date.iso8601==date来检查这个。有什么好的方法吗？编辑解释我的环境，并改变问题的范围。因此，我的项目将使用jsapiFullCalendar，这就是我需要iso8601字符串格式的原因。我想知道更好或正确的方法是什么，以正确的格式将日期保存在数据库中，或者让ActiveRecord完成它们的工作并在我需要时间信息时对其进行操作。 最佳答案 我不太明白你的问题。我假设您想检查
我的日期格式如下:"%d-%m-%Y"(例如，今天的日期为07-09-2015)，我想看看是不是在过去的七天内。谁能推荐一种方法？ 最佳答案 你可以这样做:require"date"Date.today-7 关于ruby-检查日期是否在过去7天内，我们在StackOverflow上找到一个类似的问题： https://stackoverflow.com/questions/32438063/
我有一些代码在几个不同的位置之一运行:作为具有调试输出的命令行工具，作为不接受任何输出的更大程序的一部分，以及在Rails环境中。有时我需要根据代码的位置对代码进行细微的更改，我意识到以下样式似乎可行:print"Testingnestedfunctionsdefined\n"CLI=trueifCLIdeftest_printprint"CommandLineVersion\n"endelsedeftest_printprint"ReleaseVersion\n"endendtest_print()这导致:TestingnestedfunctionsdefinedCommandLin
我有一个只接受一个参数的方法:defmy_method(number)end如果使用number调用方法，我该如何引发错误？？通常，我如何定义方法参数的条件？比如我想在调用的时候报错:my_method(1) 最佳答案 您可以添加guard在函数的开头，如果参数无效则引发异常。例如:defmy_method(number)failArgumentError,"Inputshouldbegreaterthanorequalto2"ifnumbereputse.messageend#=>Inputshouldbegreaterthano
