【剑指offer】和为S的两个数字

方法1： 二分 复杂度O(n)

import java.util.ArrayList;
import java.util.Arrays;

public class Solution {
    public ArrayList<Integer> FindNumbersWithSum(int[] array, int sum) {
        ArrayList<Integer> list = new ArrayList<Integer>();
        for (int i = 0; i < array.length; i++) {
            if (array[i] > sum) {
                break;
            }
            // Arrays.binarySearch返回值：
            // 若找到元素，则返回该元素下标；否则返回-（插入点）-1
            int ans = Arrays.binarySearch(array, i + 1, array.length, sum - array[i]);
            if (ans >= 0) {
                list.add(array[i]);
                list.add(array[ans]);
                break;
            }
        }
        return list;
    }
}

方法2： 首尾指针 复杂度O(n)

import java.util.ArrayList;

public class Solution {
    public ArrayList<Integer> FindNumbersWithSum(int[] array, int sum) {

        ArrayList<Integer> list = new ArrayList<Integer>();
        int l = 0, r = array.length - 1;
        while (l < r) {
            if (array[l] + array[r] == sum) {
                list.add(array[l]);
                list.add(array[r]);
                break;
            } else if (array[l] + array[r] > sum) {
                r--;
            } else {
                l++;
            }
        }
        return list;
    }

}