LeetCode（1） ----- Two Sum

感觉自己太水了，所以先定一个小目标，每天刷一道算法题。
然后网站的话，就选择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.

样例：Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

翻译：给两个整形数组，返回两个数字的索引值，这两个数字的和应该是给定目标整数
条件是：确保每一个输入都有一个答案，且不能用同一个数字两次

然后给出我的Code

class Solution {
    public int[] twoSum(int[] nums, int target) {
        for(int a = 0;a < nums.length;a++){
            for(int b = a+1;b<nums.length;b++){
                if(nums[a]+nums[b] == target){
                   return new int[]{a,b};            
                }
            }
        }
        return null;
    }
}

对于我这种小菜鸡，能做出来题就不错了，还没来得及考虑复杂度。

思路是遍历两个数字来相加等于目标值，但是要注意题目要求，一个数字不能用两次，所以b的初始值是a+1;
时间复杂度O（n²）

然后提交通过，去查看solution，代码是一样的，然后去查看discuss，找到最佳答案如下：

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

大致的思路是采用HashMap来储存目的值来和当前值比较，消耗空间来换取时间，时间复杂O（n），果然是我太年轻！

继续奋斗！