Java 在排序数组中找到三个数字的所有组合,它们的和比一个数字小

2022-10-15 07:56:51标签javaarraystime-complexity
提问

标题是一口,所以我要进一步解释。这是我在计算机科学课程的介绍中提出的一个问题。大多数问题,我可以自己解决,或者在网上找到解决方案,但不是为了这个。 给定一个排序数组(int[]arr)独特的整数(正和负)。你必须发现有多少三胞胎(数组中的三个数字的组合)有一个和一个给定的数字(int num)的和。 方法签名如下: 公共静态int counttriunk(int[]arr int num) 问题是,它必须以最低的时间复杂度来完成。如果我正确地理解了对所有可能的组合进行迭代,那么循环的组合可能会给我一个O(n3)的时间复杂度。然而,我想不出其他的解决方案。 我还应该提到,数组应该被用作数组,而不需要使用像ArrayList这样的其他Java类。 任何帮助都是值得感谢的。它不需要是一个完整的代码解决方案,甚至是如何解决这个问题的一般概念。 你可以尝试两种方法来解决这个3和较小的问题: 因为数组已经排序了,你可以在任何一种算法中跳跃。 二进制搜索方法O(n ^ 2logn) 两指针方法:O(n ^ 2) 我将尝试两指针方法。看一下Leetcode的2-sum和3-sum问题,因为这是它的变体。祝你好运!

回答

▼版权说明

相关文章也很精彩
推荐内容
更多标签
相关热门
全站排行
随便看看

错说cuoshuo.com——程序员的报错记录

部分内容根据CC版权协议转载,如果您希望取消转载请发送邮件到cuoshuo8@163.com

辽ICP备19011660号-5