和为S的两个数字

最直观的当然是暴力解：

import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> FindNumbersWithSum(int[] a, int sum) {
        ArrayList<Integer> ret = new ArrayList<>();
        if (a == null || a.length < 2)
            return ret;
        for (int i = 0; i < a.length - 1; ++i) {
            for (int j = a.length - 1; j > i; --j) {
                if (a[i] + a[j] == sum) {
                    ret.add(a[i]);
                    ret.add(a[j]);
                    return ret;
                }
            }
        }
        return ret;
    }
}

由于是递增有序的数组，又想到了二分查找的方式：

import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> FindNumbersWithSum(int[] a, int sum) {
        ArrayList<Integer> ret = new ArrayList<>();
        if (a == null || a.length < 2) {
            return ret;
        }
        for (int i = 0; i < a.length - 1; ++i) {
            int x = find(a, i + 1, a.length - 1, sum - a[i]); // 查找 sum - a[i]
            if (x != -1) {
                ret.add(a[i]);
                ret.add(a[x]);
                return ret;
            }
        }
        return ret;
    }

    private int find(int[] a, int start, int end, int k) {
        int ret = -1;
        while (end >= start) {
            int mid = (start + end) >> 1;
            if (a[mid] == k) {
                return mid;
            } else if (a[mid] < k) {
                start = mid + 1;
            } else {
                end = mid - 1;
            }
        }
        return ret;
    }
}

看了一下题解，发现里面的双指针法非常巧妙，顺着思路实现了一下：

import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> FindNumbersWithSum(int[] a, int sum) {
        ArrayList<Integer> ret = new ArrayList<>();
        if (a == null || a.length < 2) {
            return ret;
        }
        for (int i = 0, j = a.length - 1; i < j; ) {
            if (a[i] + a[j] == sum) {
                ret.add(a[i]);
                ret.add(a[j]);
                return ret;
            } else if (a[i] + a[j] > sum) {
                --j;
            } else {
                ++i;
            }
        }
        return ret;
    }
}