开始第一道LeetCode编程题吧！

原题：

给定一个整数数组和一个目标值，找出数组中和为目标值的两个数。

你可以假设每个输入只对应一种答案，且同样的元素不能被重复利用。

示例:

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

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

原题链接

解答：

这道题无疑是比较简单的，就是在数组里找到两个数相加等于给定的数target，我们首先可以想到暴力循环，直接遍历数组，找出与nums[i]相加为target的元素，然后返回下标。

实现代码如下：

    /**
     *
     * 暴力方式，直接遍历数组，找出与nums[i]相加为target的元素，然后返回下标。
     * 因为要循环两次，时间复杂度为O(n * n)
     * 空间复杂度为O(1)。
     *
     * @param nums
     * @param target
     * @return
     */
    public int[] twoSum(int[] nums, int target) {
        int len = nums.length;

        for (int i = 0; i < len; i++) {
            for (int j = i + 1; j < len; j++) {
                if ((nums[i] + nums[j]) == target) {
                    return new int[] {i, j};
                }
            }
        }

        throw new IllegalArgumentException("No two sum solution");
    }

因为要循环两次，时间复杂度为O({% math %}n^2{% endmath %});

空间复杂度为O(1）。

第二种解法：

上面是利用暴力循环进行的，简单来说就是遍历了两次。我们可以直接将遍历的结果存到map中，因为map有key， value的结构，可以将数组元素的值作为key，下标为value存入map中。在一次遍历中，可以先计算出target - nums[i]，然后去map中判断key是否存在，如果存在，证明符合要求，直接将value取出来返回即可。

实现代码如下：

    /**
     * 利用一个map将遍历过的数组的元素存起来，然后通过map来判断target - nums[i]元素是否存在，
     * 只需遍历一次即可，所以时间复杂度为O(n)；
     * 在最坏的情况下，需要map需要存储数组的所有元素，所以空间复杂度为O(n)。
     *
     * @param nums
     * @param target
     * @return
     */
    public int[] twoSum2(int[] nums, int target) {
        Map<Integer, Integer> a = new HashMap<>();

        for (int i = 0; i < nums.length; i++) {
            int x = target - nums[i];
            if (a.containsKey(x)) {
                return new int[] {a.get(x), i};
            }

            a.put(nums[i], i);
        }

        throw new IllegalArgumentException("No two sum solution");
     }

时间复杂度

只需遍历一次即可，所以时间复杂度为O(n)；

空间复杂度

在最坏的情况下，需要map需要存储数组的所有元素，所以空间复杂度为O(n)。

Java实现及测试

其他解法欢迎补充~