数列求和 腾讯编程马拉松
给定n个数字和一个范围[x,y],求从这n个数字中任意取出一些数字,使得它们的和在范围[x,y]中有多少种取法。 输入: 输入第一行为整数case,case
下载地址
用户评论
运用了很多STL,不错
感谢分享。看了下,大概就是把数组分成前后两部分运行;之后把每部分的所有组合的值保留起来放在leftSet和rightSet里,如果两个集合里有一对元素的和满足条件则加到总结果中去。代码中对集合进行了排序以加快寻找符合条件对的过程。如果在寻找符合条件对的时候用二分查找,则可变成a(n)=2*a(n/2)+O((n/2)!),则复杂度可将为O(logn*(n/2)!)。(后面部分只是粗略算了下,如果错了请轻拍-_-||)
可以运行,没有注释。
可以运行,但是没有注释,没有讲实现原理。