Foobar Lucky Triple问题:组合枚举法为何无法通过全部测试用例
待解决编程问题
编写函数solution(l),入参为正整数列表l,统计满足索引规则i < j < k的「幸运三元组」(li, lj, lk)的数量,相关规则如下:
- 列表长度取值范围为
[2, 2000] - 幸运三元组判定规则:元组
(x,y,z)满足x整除y,且y整除z,例如(1,2,4)即为符合要求的三元组 - 列表元素取值范围为
[1, 999999],最终返回结果符合32位有符号整数范围 - 若列表中不存在符合条件的三元组,直接返回
0
示例:输入列表
[1,2,3,4,5,6]时,符合要求的三元组为[1,2,4]、[1,2,6]、[1,3,6],共3个,因此返回值为3。
个人实现与诉求
当前编写的解法只能通过前两个测试用例,希望排查现有解题思路的问题,不需要直接提供正确答案,现有代码如下:
def my_solution(l): from itertools import combinations if 2<len(l)<=2000: l = list(combinations(l, 3)) l= [value for value in l if value[1]%value[0]==0 and value[2]%value[1]==0] #l= [value for value in l if (value[1]/value[0]).is_integer() and (value[2]/value[1]).is_integer()] if len(l)<0xffffffff: l= len(l) return l else: return 0
现有思路的问题说明
- 核心性能问题:直接调用
combinations枚举所有三元组的做法时间复杂度为O(n³),当列表长度接近上限2000时,需要枚举的三元组总量超过130亿,运算量远超常规代码运行的时间限制,必然会在长列表测试用例上超时失败。 - 冗余逻辑问题:代码中
if len(l)<0xffffffff的判断没有实际意义,题目已经明确说明最终结果在32位有符号整数范围内,该判断既不会修正结果,也不会提升性能,属于无效代码。 - 变量使用问题:代码中反复对入参变量
l做覆盖赋值,虽然不会直接引发功能错误,但会大幅降低代码可读性,提高调试难度。
内容的提问来源于stack exchange,提问作者PythonLearner
相关产品推荐
相关产品推荐

