题解 | #两数之和#

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param numbers int整型一维数组
     * @param target int整型
     * @return int整型一维数组
     */
    public int[] twoSum (int[] numbers, int target) {
        // write code here

        int[] result = {-1, -1};
        Map<Integer, List<Integer>> nubmersIndex = new HashMap<>();
        for (int i = 0; i < numbers.length; i++) {
            if (nubmersIndex.containsKey(numbers[i])) {
                nubmersIndex.get(numbers[i]).add(i + 1);
            } else {
                List<Integer> so = new ArrayList<>();
                so.add(i + 1);
                nubmersIndex.put(numbers[i], so);
            }
        }
        Arrays.sort(numbers);
        int r =  search(numbers, target);
        int diff = 0;
        for (int i = 0; i < r + 1 && i < numbers.length; i++) {
            diff = target - numbers[i];
            if (nubmersIndex.containsKey(diff)) {
                result[0] = nubmersIndex.get(numbers[i]).get(0);
                List<Integer> resList = nubmersIndex.get(diff);
                if (resList.size() > 1) {
                    result[1] = resList.get(1);
                } else {
                    result[1] = resList.get(0);
                }

                break;
                //return new int[]{i+1,nubmersIndex.get(diff)};
            }
        }
	  	Arrays.sort(result);
        return result;
    }

    public int search(int[] numbers, int target) {
        int len = numbers.length;
        int left = 0, right = len; //左闭右开所以right为len
        while (left < right) {
            int mid = left + (right - left) /
                      2; //int mid = (left+right)/2 避免整数算法溢出
            if (numbers[mid] < target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return right;
    }
}