LeetCode每天一題之兩數之和

這個LeetCode刷題系列的博客權當是為自己記一下筆記吧。博客系列會從LeetCode的第一題開始刷，同時會從零開始學習【因為我就是零/(ㄒoㄒ)/~~】。同時，如果有寫錯的地方，希望大佬們在評論區指正。

LeetCode官網

LeetCode第一題

首先需要一點點關於時間和空間複雜度的概念。

時間複雜度

首先先簡單地說一下時間複雜度：時間複雜度使用大O字母表示，不包括函數的首項和低階項，跟n有關。比如說一個程式的運行次數如下：

其中常數項運行的時間複雜度都是O(1)【無論運行次數是多麼大】。

空間複雜度

空間複雜度也就是這個演算法臨時需要的儲存單元。如果空間不隨n變化【也就是為一個常數】，那麼他的空間複雜度就是O(1);

題目如下

給定一個整數數組nums和一個目標值target，請你在該數組中找出和為目標值的那兩個整數，並返回他們的數組下標。
你可以假設每種輸入只會對應一個答案。但是，你不能重覆利用這個數組中同樣的元素【這個應該是翻譯有點問題，意思應該是target為兩個不同的數相加，不可能為一樣的數】。

示例:

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

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

解題方法一

方法一很簡單，拿前面的數跟後面所有的數進行比較，代碼如下所示：

class Solution {
    public int[] twoSum(int[] nums, int target) {
        for(int i =0;i<nums.length-1;i++){
            for(int j =i+1;j<nums.length;j++){
                       if(nums[i]+nums[j] == target){
                           int[] re = {i,j};
                           return re;
                       }
            }
        }
     return null;  
    }
}

那麼在這題中，時間複雜度：第一個for迴圈n次，第二個for迴圈n-1次

所以，時間和空間的複雜度很簡單的知道：

思考一下，如果我們可以這樣做：我們知道一個數，用target去相減，得到一個數後，再去判斷這個是否存在，如果存在則返回，這樣就可以減少時間複雜度到O(n)了，這時候神奇的HashMap就出現了。（ps:HashMap進行元素的查找時間複雜度是o(1)）【這個方法當然，emm不是我想到的/(ㄒoㄒ)/~~】

解題方法二：使用HashMap（一）

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        for(int i=0;i<nums.length;i++){
            // 將數組元素做為key，便於查找
            map.put(nums[i],i);
        }
        for(int j=0;j<nums.length;j++){
            // 獲得相減數
            int com = target - nums[j];
            // 假如存在，則比較是否重覆
            if(map.containsKey(com) && map.get(com) != j){
                return new int[]{j,map.get(com)};
            }
        }
        return null;
    }
}

時間複雜度是O(n)，空間複雜度是O(n),因為是用了HashMap去儲存元素。

本來以為這樣很牛逼了，但是現在發現還有更牛逼的操作

在上面的操作中，我們是使用HashMap存儲所有數組，但是如果結果就在第一個和第二個呢？那豈不是浪費空間？這時候我們就可以先比較，後放數組。

解題方法二：使用HashMap（二）

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

在LeetCode提交後查看了一下時間，後面兩種速度大約比第一種快了3倍。

以後我還是老老實實刷題吧。

謹守本心，做到極致 ——《將夜》