java这个解决方案可以被优化吗?
给定一个数组,比如L=[3,4,6,7,2,1]和一个整数Z=8,找到属于L的两个整数X,Y,这样X+Y=Z
这里有一个可能的解决方案-
public static void findIntegersSum(List<Integer> list, int z) {
for(int i = 0 ;i < list.size(); i++) {
for(int j = i+1 ; j< list.size(); j++) {
if(list.get(i) + list.get(j) == z) {
System.out.println(" X = " + list.get(i) + "\t Y=" + list.get(j));
return;
}
}
}
System.out.println(" No match found !!");
}
问题是-我们可以优化上述解决方案吗
# 1 楼答案
如果我们允许使用O(R)的附加空间,其中R是数字的范围,则此方法可以在O(n)时间上求解。下面是实现
# 2 楼答案
您可以使用Set数据类型的实现来实现这一点。集合通常实现为Hash table(Java中的HashSet)或Binary Search Tree(Java中的TreeSet)。哈希表实现通常使用更多内存,但在平均情况下具有恒定时间O(1)查找和插入,树实现使用线性内存,但在平均情况下具有O(logn)查找和插入
使用此数据结构的伪代码如下所示:
此解决方案是O(n)或O(n log n)而不是O(n^2)
# 3 楼答案
下面的解决方案将更加优化,因为它可以在每个步骤减少列表大小
# 4 楼答案
排序,之后只需在数组上迭代一次,并检查匹配值是否在数组中。这只会对大型阵列更有效