LeetCode 題解（一）：Two Sum

LeetCode : two sum

第一次寫博客，算是熟悉這些編輯環境吧，本來是打算在csdn上用markdown寫的，結果改了博客介紹就被關閉了，暈死。。。好了，話不多說，今天打算拿LeetCode上的第一題：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.

例子：Given nums = [2, 7, 11, 15], target = 9,

　　　Because nums[0] + nums[1] = 2 + 7 = 9,

　　   return [0, 1].

分析：看到題目之後瞭解到需求為找到數組中兩個數之和滿足給定target的下標，保存在一個數組中返回。一個簡單的思路就是像冒泡排序一樣利用兩層遍歷來
找到結果。複雜度為o(n^2).

 1     public int[] twoSum(int[] nums, int target) {
 2         int [] result=new int [2];
 3         for(int i=0;i<nums.length;i++){
 4             for(int j=i+1;j<nums.length;j++){
 5                 if((nums[i]+nums[j])==target){  //遍曆數組，找到滿足的兩個數的下標保存在數組中
 6                     result[0]= nums[i];
 7                     result[1]= nums[j];
 8                 }
 9             }
10         }
11         if(result[0]==result[1]&&result[0]==0){   //這一步很多人不會註意，要判斷原來初始化的數組中的數是否滿足都不為0的要求
12             return null;
13         }else{
14             return result;
15         }
16         
17     }

其實這道題是一年前寫的了，當時也就是為了通過而通過，所以沒管複雜度的問題，其實這不是一個好習慣，今天第一次寫博客又想了下，找到了更好的方法，利用
hashmap可以實現o(n)：

 1     public static int[] twosum(int[] num,int target){
 2         HashMap<Integer,Integer> map = new HashMap<>();  //構建hashmap
 3         for (int i = 0;i<num.length;i++){
 4             if (map.containsKey(target-num[i])){   //判斷當前map中有木有與num[i]和為target的鍵，如果有則找到這對鍵值，
 5                  return new int[]{map.get(target-num[i]),i+1};  // 和當前下標組成結果
 6             }else {
 7                 map.put(num[i],i);
 8             }
 9         }
10         return null;
11     }

　　那麼現在就算是完成這道題了吧，發現寫博客真的不是一件那麼簡單的事，希望能堅持下來吧，最後來一張我gakki的美照紀念一下