add Two Numbers

原题链接

description

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

思路分析：

• 方案1： 最简单的方法是使用双层循环暴力搜索，都每个位置的元素，从该位置后到末尾进行循环遍历，知道找到满足条件的位置， 但这种方法时间复杂度为o(n^2), 时间复杂度太高

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 solution");}

• 方案2： 上一步之所以需要o(n^2)，是因为对于每次遍历的位置都没有任何记录，下次需要重新遍历，如果把之前的遍历过程记录下来，是不是就可以一次遍历即可， 记录遍历过的元素和位置之间的关系很容易想到使用HashMap，这其实是一种典型的空间换时间的例子，时间复杂度o(n), 空间复杂度O(n)

 public int[] twoSum(int[] nums, int target) {
        HashMap<Integer, Integer> map =new HashMap<>();
        for(int i=0;i<nums.length;i++){
            if(map.containsKey(target-nums[i])){
                return new int[]{map.get(target-nums[i]),i};
            }
            map.put(nums[i],i);
        }
        return null;
    }