给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的两个整数。
你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。

示例:

给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

解法：

1.暴力解决：int[]

时间复杂度为O(n^2)，空间复杂度为O(1)

public static int[] twoSum(int[] nums, int target) {
       //定义一个存放2个数的数组，存储结果并返回
       int[] rs=new int[]{0,0};
       for (int i = 0; i < nums.length; i++) {
           for (int j = i+1; j < nums.length; j++) {
               if (nums[i]+nums[j]==target) {
                   rs[0]=i;
                   rs[1]=j;
                   return rs;
               }
           }
       }
       return rs;
   }

public static int[] twoSum1(int[] nums, int target) {
       for(int i=0;i<nums.length;i++)
           for (int j = i+1; j < nums.length; j++) {
               if (nums[i]+nums[j]==target) {
                   //直接return 一个new的新数组
                   return new int[]{i,j};
               }
           }
       //主动抛出异常
       throw new IllegalArgumentException("no such two nums");
   }

2.两遍哈希表：HashMap

时间复杂度为O(n)，空间复杂度为O(n)，以空间换时间

//两遍哈希表
    public static int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map=new HashMap<>();
        //第一遍哈希表：将给定的数存进map中
        for (int i = 0; i < nums.length; i++) {
            map.put(nums[i], i);
        }
        for (int i = 0; i < nums.length; i++) {
            int rs=target-nums[i];
            //map查询时间为O(1)
            if(map.containsKey(rs)&&map.get(rs)!=i){
                return new int[]{i,map.get(rs)};
            }
        }
        throw new IllegalArgumentException("no such two nums");
    }

3.一遍哈希表：HashMap

时间复杂度为O(n)，空间复杂度为O(n)

public static int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map=new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int rs=target-nums[i];
            if (map.containsKey(rs)) {
                //与两遍哈希表输出顺序相反
                return new int[]{map.get(rs),i};
            }
            //不需要提前存储，边判断边存储
            map.put(nums[i], i);
        }
        throw new IllegalArgumentException("no such two nums");
    }

知识点：

1.哈希表的特点：保持数组中的元素与其索引相对应；支持以恒定时间查找为O(1)。
2.空间复杂度：运行程序时所需的额外空间。
3.主动抛异常：
throw new IllegalArgumentException("no such two nums");