167. Two Sum II

原题链接：https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/description/
这道题目蛮有意思的，有点难度哦：

import java.util.Arrays;

/**
 * Created by clearbug on 2018/2/26.
 */
public class Solution {

    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(Arrays.toString(s.twoSum1(new int[]{2, 7, 11, 15}, 9)));
        System.out.println(Arrays.toString(s.twoSum1(new int[]{2, 7, 11, 15}, 18)));

        System.out.println(Arrays.toString(s.twoSum2(new int[]{2, 7, 11, 15}, 9)));
        System.out.println(Arrays.toString(s.twoSum2(new int[]{2, 7, 11, 15}, 18)));
    }

    /**
     * 方法一：最黄最暴力
     *
     * @param numbers
     * @param target
     * @return
     */
    public int[] twoSum1(int[] numbers, int target) {
        for (int i = 0; i < numbers.length; i++) {
            for (int j = i + 1; j < numbers.length; j++) {
                if (numbers[i] + numbers[j] == target) {
                    return new int[]{i + 1, j + 1};
                }
            }
        }

        return null;
    }

    /**
     * 方法二：分析方法一可知，方法一有两层循环，时间复杂度极高。然后，我想可以使用类似二分查找的思想来优化，但是却想不出究竟怎样完美的用上
     *      二分查找思想，然后就去看了下提交区运行时间最低的答案，瞬间明白了。。。后来，写了下实现，才发现刚才那瞬间自己根本没明白，现在才
     *      稍微明白点了。。。
     *
     * @param numbers
     * @param target
     * @return
     */
    public int[] twoSum2(int[] numbers, int target) {
        int start = 0, end = numbers.length - 1;
        while (start < end) {
            if (numbers[start] + numbers[end] == target) {
                return new int[]{start + 1, end + 1};
            } else if (numbers[start] + numbers[end] < target) {
                // move start forward
                start = smallestLargerOrFirstEqual(numbers, start, end, target - numbers[end]);
            } else { // numbers[start] + numbers[end] > target
                // move end backward
                end = largestSmallerOrLastEqual(numbers, start, end, target - numbers[start]);
            }
        }

        return null;
    }

    private int smallestLargerOrFirstEqual(int[] numbers, int start, int end, int target) {
        while (start <= end) {
            int middle = (start + end) / 2;
            if (numbers[middle] == target) {
                return middle;
            } else if (numbers[middle] < target) {
                start = middle + 1;
            } else {
                end = middle - 1;
            }
        }

        return start;
    }

    private int largestSmallerOrLastEqual(int[] numbers, int start, int end, int target) {
        while (start <= end) {
            int middle = (start + end) / 2;
            if (numbers[middle] == target) {
                return middle;
            } else if (numbers[middle] < target) {
                start = middle + 1;
            } else {
                end = middle - 1;
            }
        }

        return end;
    }

}