package org.lep.leetcode.twosum;import java.util.Arrays;import java.util.HashMap;import java.util.Map;/** * source:https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/#/description * Created by lverpeng on 2017/6/21. * * Given an array of integers, find two numbers such that they add up to a specific target number. * * The function twoSum should return indices of the two numbers such that they add up to the target, * where index1 must be less than index2. Please note that your returned answers (both index1 and index2) * are not zero-based. * * You may assume that each input would have exactly one solution. * * Input: numbers={2, 7, 11, 15}, target=9 * Output: index1=1, index2=2 * */public class TwoSum {    public static void main(String[] args) {        TwoSum twoSum = new TwoSum();        int[] numbers = {2, 7, 11, 15};        System.out.println(Arrays.toString(twoSum.twoSum(numbers, 9)));        System.out.println(Arrays.toString(twoSum.twoSumUseHash(numbers, 9)));    }    /**     * 最简单的方法对于数组中每一个数，依次遍历其后每一个数字，直到找到两个和为target的数字     * 时间复杂度：O(n^2)     * 空间复杂度：O(1)     *     * @param numbers     * @param target     * @return     */    public int[] twoSum (int[] numbers, int target) {        int[] result = new int[2];        for (int i = 0; i < numbers.length; i ++) {            for (int j = i; j < numbers.length; j++) {                if ((numbers[i] + numbers[j]) == target) {                    result[0] = i + 1;                    result[1] = j + 1;                    return result;                }            }        }        return result;    }    /**     * 由于上面第二次循环只是在查找一个数，那么就可以使用hash来查找，将第一个对应的另一个加数依次添加到hash表里，降低时间复杂度     * 时间复杂度：O(n)     * 空间复杂度：O(n)     *     * @param numbers     * @param target     * @return     */    public int[] twoSumUseHash (int[] numbers, int target) {        int[] result = new int[2];        Map
    
      needOtherNum = new HashMap
     
      (); // 
      
               for (int i = 0; i < numbers.length; i++) {            // 如果当前num是前面数字所需要的另外一个加数，说明找到了            if (needOtherNum.containsKey(numbers[i])) {                result[0] = needOtherNum.get(numbers[i]) + 1;                result[1] = i + 1;                break;            } else {                // 如果没有找到，则把当前数字所需要的另外一个加数添加到map中                needOtherNum.put(target - numbers[i], i);            }        }        return result;    }}