01 题目描述： （简单难度）
给定⼀个数组和⼀个⽬标和，从数组中找两个数字相加等于⽬标和，输出这两个数字的下标。
举例：
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1]
提示：
2 <= nums.length <= 104
-109 <= nums[i] <= 109
-109 <= target <= 109
解法一：
使用暴力方法，双重for循环遍历数组的所有元素，若与目标值target相等，则返回两个数字的下标即可
public int[] twoSum(int[] nums, int target) { int []ans=new int[2]; //定义一个数组，用来存放两个值 for(int i=0;i<nums.length;i++){ //遍历数组第一个元素值 for(int j=(i+1);j<nums.length;j++){ //遍历数组第一个元素的下一个值 if(nums[i]+nums[j]==target){ //判断两数相加是否与目标值相等 ans[0]=i; ans[1]=j; return ans; } } } return ans; }
时间复杂度：o(n²)
空间复杂度：o(1)
解法二：
从解法一的代码中可以看出在第二层for循环的代码为：
for(int j=(i+1);j<nums.length;j++){ if(nums[i]+nums[j]==target)
相当于以下代码：
for(int j=(i+1);j<nums.length;j++){ int sub = target - nums[i]; if(nums[j]==sub)
第二层for循环的目的是遍历所有元素，时间复杂度为o(n)，此时我们选择用HashTable集合，便可以不用遍历所有所有元素，可以把数组的每个元素保存为 hash 的 key，下标保存为 hash 的 value，此时只用来判断sub在不在hash里面的key中就可以了，但开辟了新的内存空间，所以此时的空间复杂度为o(n)
public int[] twoSum(int[] nums, int target) { Map<Integer,Integer> map=new HashMap<>(); for(int i=0;i<nums.length;i++){ map.put(nums[i],i); //添加元素到Map集合中去num[i]为值，i为索引 } for(int i=0;i<nums.length;i++){ int sub=target-nums[i]; if(map.containsKey(sub)&&map.get(sub)!=i){ //map.containsKey(sub)为Map集合的一个方法，用于检查Map集合中是否包含Key(sub) //map.get(sub)!=i 用来确保找到的两个数的索引不同 return new int[]{i,map.get(sub)}; } } throw new IllegalArgumentException();//抛出异常 }
时间复杂度：o(n)
空间复杂度：开辟了hash的空间，所以空间复杂度为o(n)
解法三：
在解法二中，我们可以发现当用了Hashtable后，两个for循环就一样了，此时我们可以将一样的内容合并起来，（注意:合并相同代码并没有改变算法的复杂度）
public int[] twoSum(int[] nums, int target) { Map<Integer,Integer> map=new HashMap<>(); for(int i=0;i<nums.length;i++){ int sub=target-nums[i]; if(map.containsKey(sub)){ return new int[]{i,map.get(sub)}; } map.put(nums[i], i); } throw new IllegalArgumentException()//异常抛出; }
时间复杂度：o(n)
空间复杂度：o(n)
总结：
本题目时LeetCode的第一道题 题目难度为简单，在掌握基本的方方法后，可以考虑优化算法，降低时间和空间的复杂度，在解法二和解法三中，都降低了用暴力破解的时间复杂度o(n²)到o(n),但因开辟了hash,时间复杂度从o(1)到哦o(n),但可以加深我们的hash表的运用和对Map集合的使用。
