我的LC之路-1. Two Sum

写在前面：在LeetCode上做的题，代码基本都是我自己写的，效率有好有坏，仅供参考。
有少数几道题苦思冥想做不出来的，可能会借鉴网上大神的解法，然后再自己编写，借鉴过他人解法的题会有说明。
本人不是算法出身，语言基本靠自学，有任何错误理解或者不当举措，还请各位大侠手下留情并不吝赐教！万分感谢~

为防止各位看客还得来回切换看题干，顺便把题贴过来（其实是自己懒得来回捯~哈哈）：

1. Two Sum

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].

解题思路：

刚拿到这道题，立马想到的是遍历两次数组，挨个相加，再和target比较，这样方法虽然比较简单粗暴，但效率肯定相当底下。

我的原则一般是：以解决问题为主要。

所以，不管复杂度怎样，先能做出来再说。

代码如下：

 1 public class Solution {
 2     public int[] twoSum(int[] nums, int target) {
 3         int[] res = null;
 4         for(int i=0;i<nums.length;i++){
 5             for(int j=nums.length-1;j>=0;j--){
 6                 if(nums[i]+nums[j]==target&&i!=j){
 7                     res = new int[2];
 8                     res[0] = i;
 9                     res[1] = j;
10                 }
11             }
12         }
13         return res;
14     }
15 }

这样提交了一次，居然过了，看来LeetCode第一题并不打算打击大家的积极性~哈哈

题做完了，但这做法还是比较笨，于是准备思考一下如何优化性能。

想来想去，感觉自己水平有限，能够改良的地方并不多。。。

只能凭借哈希表这个强力工具来提高下效率，hashmap里的containsKey方法，可以快速的查找出已存入hashmap里的数值是否包含key值。根据这一点特性，可以快速的对数值进行比较。

为了看看复杂度，我郑（zhuang）重（mu）其（zuo）事（yang）的看了下HashMap里的containsKey这个方法，查到源码，发现只有这么简单的一句：

1     public boolean containsKey(Object key) {
2         return getNode(hash(key), key) != null;
3     }

继续找getNode方法会发现，大概意思是根据key的hash值来进行查找，源码较为复杂，我看得比较吃力，这里就先不做深究啦！

回到我们的题目，利用hashmap对方法进行更改：

 1 class Solution {
 2     public int[] twoSum(int[] nums, int target) {
 3         int temp = 0;
 4         int[] result = {0,0};
 5         Map<Integer,Integer> m = new HashMap<>();
 6         for(int i = 0;i<nums.length;i++){
 7             temp = target-nums[i];
 8             if(m.containsKey(temp)){
 9                 result[0] = m.get(temp);
10                 result[1] = i;
11             }
12             m.put(nums[i],i);
13         }
14 
15         return result;
16 
17     }
18 }

提交之后看了下时间，这个耗时10ms，上面是73ms。看来结果确实快了不少。

这里将值设为key，将下标作为value是因为最后结果需要输出的是下标，这样比较方便。更为重要的是，题目中明确表示have exactly one solution。

不然将数组里的值作为key，就无法达到解题的效果。因为1根据hashmap的特性，后存入的key会替换掉先存入的key，若有多个解的话，例如：nums = [2, 7, 7 ,11, 15], target = 9，这样只能得到[0, 2]，得不到[0, 1]的答案了：）

JAVA学习网

分类

我的LC之路-1. Two Sum

1. Two Sum