和为S的两个数字

问题描述

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

思路分析

核心思想就是设置两个变量，起始变量start和指向尾的变量end，刚开始先比较和cur=start+end与s的和，如果比s大说明最后的end数较大，end应前移，直至小于等于，反之则是start较小，start应后移。直至最后等于为止，此时因为end处于最大的情况，所以start处于最小，也是所要找的两个数。但是如果不存在，则返回空

码上有戏

public ArrayList<Integer> FindNumbersWithSum(int [] array,int sum) {
        ArrayList<Integer> list=new ArrayList<Integer>();
         ArrayList<Integer> lists=new ArrayList<Integer>();
        if(array==null||sum<=0) return list;
        int start=0;
        int end=array.length-1;
        int curSum=array[start]+array[end];
        while(start<end){
            if(curSum==sum){
                    list.add(array[start]);
                    list.add(array[end]);
                }
            while(curSum>sum){
                end--;
                 curSum=array[start]+array[end];
                if(curSum==sum){
                    list.add(array[start]);
                    list.add(array[end]);
                }
            }
            start++;  
            curSum=array[start]+array[end];
        }
        if(list.size()==0)return list;
        lists.add(list.get(0));
        lists.add(list.get(1));
        return lists;
    }