題目描述
輸入一個遞增排序的數組和一個數字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; }新聞熱點
疑難解答
