【LeetCode】统计特殊四元组 Java 题解
题目描述
给你一个 下标从 0 开始 的整数数组 nums ,返回满足下述条件的 不同 四元组 (a, b, c, d) 的 数目 :
nums[a] + nums[b] + nums[c] == nums[d] ,且 a < b < c < d
复制代码
思路分析
今天的算法题目统计特殊的四元组。题意简单明了,需要分别 nums[a] + nums[b] + nums[c] == nums[d] ,且 a < b < c < d 两个条件。
首先,我们可以使用朴素解法得出这个题目的答案,观察朴素解法,发现有重复计算,时间复杂度较高。观察分析题目,我们可以采用倒序遍历,结合 hashmap, 可以减少一次循环。具体实现代码如下,供参考。
通过代码
朴素解法
复制代码
优化解法
复制代码
总结
朴素解法的时间复杂度是 O(n * n * n * n), 空间复杂度是 O(1)
优化解法的时间复杂度是 O(n * n * n), 空间复杂度是 O(n)
坚持算法每日一题,加油!
版权声明: 本文为 InfoQ 作者【HQ数字卡】的原创文章。
原文链接:【http://xie.infoq.cn/article/80fff86053d3f5c7925a1b234】。文章转载请联系作者。
评论