【剑指Offer】和为s的两个数字VS和为s的连续正数序列

题目一

输入一个递增排序的数组和一个数字s，在数组中查找两个数，使得它们的和正好是s。如果有多对数字的和等于s，输出任意一对即可。

实现

public ArrayList<Integer> FindNumbersWithSum(int[] array, int sum) {
    ArrayList<Integer> list = new ArrayList<>();

    if (array == null || array.length < 2)
        return list;
    
    int start = 0;
    int end = array.length - 1;

    while (start < end) {
        if (array[start] + array[end] < sum)
            start++;
        else if (array[start] + array[end] > sum)
            end--;
        else {
            list.add(array[start]);
            list.add(array[end]);
            return list;
        }
    }

    return list;
}

题目二

输入一个正数s，打印出所有和为s的连续正数序列（至少含有两个数）。例如输入15，由于1+2+3+4+5=4+5+6=7+8=15，所以结果打印出3个连续序列1～5、4～6和7～8。

实现

public ArrayList<ArrayList<Integer>> FindContinuousSequence(int sum) {
    ArrayList<ArrayList<Integer>> results = new ArrayList<>();

    if (sum < 3)
        return results;

    int start = 1;
    int end = 2;
    int middle = (sum + 1) / 2;
    int current = start + end;

    while (start < middle) {
        if (current < sum) {
            end++;
            current += end;
        }
        else if (current > sum) {
            current -= start;
            start++;
        }
        else {
            ArrayList<Integer> result = new ArrayList<>();
            findContinuousSequence(result, start, end);
            results.add(result);
            current -= start;
            start++;
            end++;
            current += end;
        }
    }

    return results;
}

private void findContinuousSequence(ArrayList<Integer> result, int start, int end) {
    for (int i = start; i <= end; i++)
        result.add(i);
}