2. import java.util.Arrays;
    4. /**
    5.  * 给定一个整数数组 nums和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那两个整数，并返回它们的数组下标。
    6.  * 你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
    7.  * 你可以按任意顺序返回答案。
    8.  *
    9.  *
    10.  * 示例 1：
    11.  *
    12.  * 输入：nums = [2,7,11,15], target = 9
    13.  * 输出：[0,1]
    14.  * 解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
    15.  * 示例 2：
    16.  *
    17.  * 输入：nums = [3,2,4], target = 6
    18.  * 输出：[1,2]
    19.  * 示例 3：
    20.  *
    21.  * 输入：nums = [3,3], target = 6
    22.  * 输出：[0,1]
    23.  *
    24.  * 来源：力扣（LeetCode）
    25.  * 链接：https://leetcode-cn.com/problems/two-sum
    26.  */
    27. public class TwoNumSum {
    29.     public static int[] solve(int[] num,int target){
    30.         int[] result = new int[2];
    31.         for(int i = 0;i<num.length;i++){
    32.             for(int j = 0 ;j<num.length;j++){
    33.                 if(i!=j){
    34.                     if(num[i]+num[j] == target){
    35.                         result[0] = i;
    36.                         result[1] = j;
    37.                     }
    38.                 }
    39.             }
    40.         }
    41.         return result;
    42.     }
    45.     //先排序，排序完成在数组里面查找对应的下标,使用二分查找，找到了再去检索原数组 o(nlogn)+o(nlogn)+n ->o(nlogn)
    46.     public static int[] solve2(int[] num,int target){
    47.         int[] result = new int[2];
    48.         int copy[] = new int[num.length];
    49.         System.arraycopy(num,0,copy,0,num.length);
    50.         Arrays.sort(copy);
    51.         int x =0,y =0;
    52.         boolean find =false;
    53.         for(int i =0;i<copy.length-1;i++) {
    54.             if(copy[i]*2 <= target) {
    55.                 int index = Arrays.binarySearch(copy, i+1 , copy.length, target - copy[i]);
    56.                 if (index > 0) {
    57.                     find = true;
    58.                     x = copy[i];
    59.                     y = copy[index];
    60.                 }
    61.             }
    62.         }
    63.         if(find){
    64.             for (int i =0;i<num.length;i++) {
    65.                 if(num[i] == x){
    66.                     result[0] = i;
    67.                 }else if(num[i] == y){
    68.                     result[1] = i;
    69.                 }
    70.             }
    71.         }
    72.         return result;
    73.     }
    76.    //Hash表查找 O(n),预处理将数组中的数据放到HashMap中，再去找
    77.     public static int[] solve3(int[] num,int target){
    78.         int[] result = new int[2];
    79.         Map<Integer,Integer> indexMap = new HashMap<>();
    80.         for (int i = 0; i < num.length; i++) {
    81.             indexMap.put(num[i],i);
    82.         }
    84.         for(int i=0;i<num.length;i++){
    85.             int y = target - num[i];
    86.             if(indexMap.get(y) !=null){
    87.                 result[0] = i;
    88.                 result[1] = indexMap.get(y);
    89.             }
    90.         }
    92.         return result;
    93.     }
    97.     public static void main(String[] args) {
    98.         int[] num = {2,7,11,15};
    99.         int target = 9;
    100.         int[] result =TwoNumSum.solve2(num,target);
    101.         for(int  i =0;i< result.length;i++){
    102.             System.out.println(result[i]);
    103.         }
    104.     }
    106. }