和为s的两个数字

题目：

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

​ 例如输入数组 {1, 2, 4, 7, 11, 15} 和数字 15。由于 4+11 = 15 ，因此输出 4 和 11 。

分析：

1. 方法一：

   ​ 最直观的一个方法就是现在数组中固定一个数字，再依次判断数组中其余的 n-1个数字与它的和是不是等于S，复杂度是O(n^2)。

2. 方法二：

   ​ 我们选择数组中两个数字，如果其和等于S，那么说明我们找到了对的。如果小于S，我们希望两个数字的和在大一点，由于数组已经排好序了，所以选择较小数字后面的数字；同样，如果当两个数字的和大于输入数字的时候，我们可以选择较大数字前面的数字，因为排在数组前面的数字要小一些。

   ​ 以数组 {1, 2, 4, 7, 11, 15} 为例，定义两个指针，分别指向第一个数字1和最后一个数字15，二者的和为16大于15，所以把第二个指针前移；这时它指向11，二者的和是12，小于15；再把第一个指针后移，这时它指向2，和是13，小于15；再后移，指向4，和是15。正好是要求的结果。

代码：

方法二实现：

class TwoNumSumSolution {

    public static List<Integer> findNumbers(int[] data, int sum) {

        List<Integer> resultList = new ArrayList<>();

        if (null == data || data.length <= 0) {
            return resultList;
        }

        int start = 0;
        int end = data.length - 1;

        while (end > start) {
            int curSum = data[start] + data[end];
            if (curSum == sum) {
                resultList.add(data[start]);
                resultList.add(data[end]);
                break;
            } else if (curSum > sum) {
                end--;
            } else {
                start++;
            }
        }

        return resultList;
    }

    public static void main(String[] args) {
        int[] data = {1, 2, 4, 7, 11, 15};
        System.out.println(Arrays.toString(findNumbers(data, 15).toArray()));
    }
}