可否简化这个算法?(python)

2021-02-24 05:21发布

RT,突然有这么一个想法,麻烦大家了。

想法是从n个整数元素的数组{an}中取出任意个使之的和m与指定整数M的差(m-M)不大于0且最大,求m的值和对应被取出的元素

如输入a1=1,a2=3,a3=6,a4=11,a5=17,M=8,则输出“a1,a2,m=4”;若输入M=10,输出“a1,a2,a3,m=10”。

笔者想到的办法是枚举,先单个对比,再两两求和,再取三个依次求和......但这样的运行效率比较低,最多需要2^n次才能得出结果,所以想问万能的博友们有没有办法能简化这个算法过程?

求解决,谢谢!

1条回答
huangzhihuan081
1楼-- · 2021-02-24 06:13

之前几个星期刚做过这个题。时间复杂度最低就是2^(n/2)级别了。一般不是算法竞赛,你电脑如果足够有电,是有机会算出来的。

当时这道题琢磨了好久才做摸出来。

太晚了我就不写答案了。给题主一个连接。

Leetcode227场周赛最后一题最接近目标值的子序列和,题里面有大佬们的答案。