算法学习：leetcode 1 两数之和

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

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。

示例:

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

思路一
有一种非常通用的解题方式，就是双层循环嵌套来解题，代码如下：

class Solution {
    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[i] + nums[j] == target) {
                        return new int[] {i,j};
                    }
                }
            }
            return null;
    }
}

相信大家都能看懂上面的逻辑，上面的解题方式的时间复杂度是O(n²)，空间复杂度是O(1).

思路二
我们可以将数组中所有的值作为key，下标作为value放到map中，然后循环数据，依次取出数组中的每个元素，计算该元素值与目标值的插值，也就是target-self=x，用这个x到map中查看是否有对应值，有则说明数组中有符合条件的数据，进行输出。

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer,Integer> map = new HashMap<>();
        for(int i=0;i<nums.length;i++) {
            map.put(nums[i],i);
        }
        for(int i=0;i<nums.length;i++) {
            int tvar = target-nums[i];
            Integer value = map.get(tvar);
            if(value != null && value.intValue() != i) {
                return new int[]{i,value};
            }
        }
        return new int[]{-1,-1};
    }
}

这里的时间复杂度是O(n)，空间复杂度O(n)

题目来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/two-sum