两数之和

题目链接:
两数之和

1.题目描述

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。

示例:

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

2.题解

2.1 两遍for循环暴力解法

第一层for循环遍历数组,第二层for循环在遍历数组的时候，用target-nums[i]得到的值与当前遍历的值进行比较，如果匹配的到就返回index数组，如果遍历结束没有匹配的值就抛出一个异常。

public  int[] twoSum(int[] nums, int target) {
        for (int i=0;i<nums.length;i++){
            for (int j=i+1;j<nums.length;j++){
                if(nums[j]==target-nums[i]){
                    return new int[]{i,j};
                }
            }
        }
        throw new IllegalArgumentException("No Two sum exception");
    }

2.2 一遍hash表

通过hash表，以空间换时间，hash表近似O(1)的查询时间。

public int[] twoSum(int[] nums, int target) {
        HashMap<Integer, Integer> map = new HashMap<>(16);
        for (int i=0;i<nums.length;i++){
            int complement = target - nums[i];
            if (map.containsKey(complement) && map.get(complement) !=i) {
                return new int[] {i,map.get(complement)};
            }
            map.put(nums[i],i);
        }
        throw new IllegalArgumentException("No Two sum exception");
    }

在这个题解中,用了一个小技巧，数组的值作为map的键，数组的下标作为map的值。
这样，通过map.containsKey()就可以方便的判断值是否存在，这样通过map.get()就会很方便的获取数组的下标。而如果使用数组下标做map的键的话，固然用map.containsValue可以判断数组中是否有这个值，但是根据值来找键就又需要遍历map。