《剑指offer》之和为S的两个数字

前言

昨天刷的和为S的连续正数序列&＃xff0c;用到的窗口双指针的方法很好用&＃xff0c;今天刚好刷到一道类似的&＃xff0c;也是用窗口双指针的&＃xff0c;一次就过的感觉还不错。

题目

输入一个递增排序的数组和一个数字S&＃xff0c;在数组中查找两个数&＃xff0c;使得他们的和正好是S&＃xff0c;如果有多对数字的和等于S&＃xff0c;输出两个数的乘积最小的。

输出描述:

对应每个测试案例&＃xff0c;输出两个数&＃xff0c;小的先输出。

分析

输出两个数的乘积最小的。这句话的理解&＃xff1f;
假设&＃xff1a;若b>a,且存在&＃xff0c;
a &＃43; b &＃61; s;
(a - m ) &＃43; (b &＃43; m) &＃61; s
则&＃xff1a;(a - m )(b &＃43; m)&＃61;ab - (b-a)m - m*m 也就是说依然是左右夹逼法&＃xff01;&＃xff01;&＃xff01;

上面这些是用来说明还是窗口双指针的方法&＃xff0c;
left&＃61;0;
right&＃61;array.length-1;
左右夹逼&＃xff0c;两个的和大于sum,right–,小于sum,left&＃43;&＃43;&＃xff0c;等于sum,退出

解法

public ArrayList FindNumbersWithSum(int [] array, int sum) {ArrayList list&＃61;new ArrayList<>();if(array&＃61;&＃61;null||array.length&＃61;&＃61;0||sum<&＃61;0){return list;}int left&＃61;0;int right&＃61;array.length-1;while(left

测试

main 方法

public static void main(String[] args) {int [] array&＃61;{1,2,3,4,5,6,7,8,9,10};Solution solution&＃61; new Solution();ArrayList list&＃61;solution.FindNumbersWithSum(array,9);for(Integer tmp:list){System.out.print(tmp&＃43;"\t");}}