面试题57(剑指offer)--和为s的数字

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

解法：

    /**
     * 数组是递增的序列，可以使用双指针指向首和尾，
     * 当首尾之和小于sum时，将头指针后移，小于sum
     * 时将尾指针前移，由于和相等的数字对，差越小
     * 乘积越大，所以第一次等于sum时，即为乘积最小
     * @param array
     * @param sum
     * @return
     */
    public ArrayList<Integer> findNumbersWithSum(int [] array, int sum) {
        ArrayList<Integer> list=new ArrayList<>();
        int len=array.length;
        if (array==null||len==0){
            return list;
        }
        int start=0,end=len-1;
        while (start<end){
            if (array[start]+array[end]>sum){
                end--;
            }else if (array[start]+array[end]<sum){
                start++;
            }else {
                list.add(array[start]);
                list.add(array[end]);
                break;
            }
        }
        return list;
    }

题目二： 和为 S 的连续正数序列。输入一个正数s，打印出所有和为s的连续正数序列(至少含有两个数)。例如，输入15，由于1+2+3+4+5=4+5+6=7+8=15，所以打印出3个连续序列1_5、46和7~8。

解法：

    /**
     * 使用双指针，初始化start指向开头，end指向第二个，
     * 若区间[start,end]的和小于sum则，end向后移动一位，
     * 若大于sum则start向后移动一位，舍掉一个数字。
     * 由于区间至少有两个数则start和end最大就是位于
     * sum的一半位置，所以start=mid时,循环结束。
     * @param sum
     * @return
     */
    public static ArrayList<ArrayList<Integer> > findContinuousSequence(int sum) {
        ArrayList<ArrayList<Integer> > res=new ArrayList<>();
        int start =1;
        int end=2;
        int mid=(sum+1)/2;
        while (start<mid){
            if (numberSum(start, end) >sum){
                start++;
            }else if (numberSum(start, end)<sum){
                end++;
            }else {
                ArrayList<Integer> temp=new ArrayList<>();
                for (int i = start; i <=end ; i++) {
                    temp.add(i);
                }
                end++;
                res.add(temp);
            }
        }
        return res;
    }

    private static int numberSum(int start, int end) {
        int res=0;
        for (int i = start; i <= end; i++) {
            res+=i;
        }
        return res;
    }