题解 | #两数之和#（附带图解）

思路:

从题中给出的有效信息：

• 找出下标对应的值相加为target
• 数组中存在唯一解

故此 可以使用 直接遍历 或者 hash表 来解答

方法一：直接遍历

具体做法：
循环遍历数组的每一个数，如果遍历的两数之和等于target，则返回两个数的下标；

import java.util.*;
public class Solution {
    /**
     * 
     * @param numbers int整型一维数组 
     * @param target int整型 
     * @return int整型一维数组
     */
    public int[] twoSum (int[] numbers, int target) {
        // write code here
        int n = numbers.length;
        int[] res = {-1, -1};
        //遍历数组
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                //判断相加值是否为target
                if (numbers[i] + numbers[j] == target) {
                    res[0] = i+1;
                    res[1] = j+1;
                    //返回值
                    return res;
                }
            }
        }
        return res;
    }
}

复杂度分析：

• 时间复杂度：O(n^2) 遍历两次数组
• 空间复杂度：O(1) 未申请额外空间

方法二 hash表

具体做法：
使用Map来降低时间复杂度，遍历数组，如果没有 （target - 当前值） 就将当前数字存入哈希表，如果有，返回该数字下标即可。

哈希表可以优化第二遍循环中对元素的检索速度，
具体过程如下图所示：

import java.util.*;
public class Solution {
    /**
     * 
     * @param numbers int整型一维数组 
     * @param target int整型 
     * @return int整型一维数组
     */
    public int[] twoSum (int[] numbers, int target) {
        // write code here
        HashMap<Integer, Integer> map = new HashMap<>();
        //遍历数组
        for (int i = 0; i < numbers.length; i++) {
            //将不包含target - numbers[i]，装入map中，包含的话直接返回下标
            if(map.containsKey(target - numbers[i])) 
                return new int[]{map.get(target - numbers[i])+1, i+1};
            else 
                map.put(numbers[i], i);
        }
        throw new IllegalArgumentException("No solution");
    }
}

复杂度分析：

• 时间复杂度：O(n) 一次遍历hash索引查找时间复杂度为O(1)
• 空间复杂度：O(n) 申请了n大小的map空间