【LeetCode】大餐计数 Java 题解
题目描述
大餐 是指 恰好包含两道不同餐品 的一餐,其美味程度之和等于 2 的幂。
你可以搭配 任意 两道餐品做一顿大餐。
给你一个整数数组 deliciousness ,其中 deliciousness[i] 是第 i 道餐品的美味程度,返回你可以用数组中的餐品做出的不同 大餐 的数量。结果需要对 109 + 7 取余。
注意,只要餐品下标不同,就可以认为是不同的餐品,即便它们的美味程度相同。
复制代码
思路分析
这个题目题意容易理解,简述成一句话就是求任意两个数之和为 2 的幂的组合数。
根据题目实际情况,采用 hashMap 数据结构实现快速查找。
通过遍历 deliciousness, 找到最大的元素,任意 2 个元素之和都小于等于元素的 2 倍,可以简化运算过程,提升效率。
代码
复制代码
总结
上述代码的时间复杂度是 O(n * n), 空间复杂度是 O(n)
坚持每日一题,加油!
版权声明: 本文为 InfoQ 作者【HQ数字卡】的原创文章。
原文链接:【http://xie.infoq.cn/article/6d293d2054c9b766d3b147346】。文章转载请联系作者。
评论