LeetCode可以说是我们程序员练习算法非常好的一个平台，借鉴大佬的文章，我在这也写下自己的学习记录，争取能够做到一千道。

题目

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]

题目大意

在数组中找到2个数之和等于给定值的数字，结果返回2个数字在数组中的下标。

解题思路

方法一：暴力枚举

最先想到的应该就是暴力枚举数组中的每一个数，寻找数组中是否存在 tager-x 。我也只想到了这种方法。
这种方法需要注意，寻找 target-x 时，同一x不能够重复使用，也就意味着: 如果 x = target - x ,那么我们不能返回同一个下标。解决方法是需要我们去匹配x后面的值

代码

package leetcode;

public class D01_TwoSum {

    public int[] twoSum_01(int[] nums, int target) {
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (nums[i] + nums[j] == target)
                    return new int[]{i, j};
            }
        }
        return new int[0];
    }

}

---

复杂度分析

* 时间复杂度：O(N²) ,其中N是数组中的元素数量。最坏的情况下数组中任意两个数都要被匹配一次。
* 空间复杂度：O(1)。

方法二：哈希表

这个是我没有想到的，hash表我确实只是知道它的基本性质，但是拿来用的话，确实没有想到。方法一的时间复杂度比较高，如果处理比较多的数据时，效率就不高了。
当使用哈希表时，可以将寻找 target - x 的时间复杂度从O(N)降到O(1)。
这样我们创建一个哈希表，对于每一个 x ，首先我们查询哈希表中是否存在 target - x ,然后将 x 插入到哈希表中，即可保证不会让 x 和自己匹配。

代码

package leetcode;

import java.util.HashMap;
import java.util.Map;

public class D01_TwoSum {

    public int[] twoSum_01(int[] nums, int target) {
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (nums[i] + nums[j] == target)
                    return new int[]{i, j};
            }
        }
        return new int[0];
    }

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

}

复杂度分析

* 时间复杂度：O(N) ,其中N是数组中的元素数量。对于每一个x,我们可以O(1)的寻找target - x
* 空间复杂度：O(N) ,其中N是数组中的元素数量，用于哈希表的开销。