题目描述
输入一个递增排序的数组和一个数字S，在数组中查找两个数，是的他们的和正好是S，如果有多对数字的和等于S，输出两个数的乘积最小的。
输出描述:
对应每个测试案例，输出两个数，小的先输出。
算法解析： 对于一个递增的有序数组，我们如果从头到尾暴力扫描，那就十分不智，如果我们将两个标志位分别设在开头和结尾，如果这两个标志位的和小于S，则将small向后移动，如果标志位的和大于s，则big前移，如果相等，我们就考虑这两个数的乘积，rank后决定是否更新结果。
代码如下：
public ArrayList<Integer> FindNumbersWithSum(int [] array,int sum) { int small = 0; int big = array.length - 1; ArrayList<Integer> result = new ArrayList<>(); if (array == null || array.length < 1){ return result; } while (small < big){ int check = array[small] + array[big]; if (check == sum){ if (result.size() == 0){ result.add(array[small]); result.add(array[big]); }else{ check = result.get(0) * result.get(1); if (check > (array[small] * array[big])){ result.clear(); result.add(array[small]); result.add(array[big]); } } small ++; }else if (check > sum){ big --; }else{ small ++; } } return result; }新闻热点
疑难解答
