【LeetCode】 1. 兩數之和 （JAVA）時間複雜度O(n2)和O(n)兩種解決方案

題目

給定一個整數數組 nums 和一個目标值 target，請你在該數組中找出和為目标值的那 兩個 整數，并傳回他們的數組下标。

你可以假設每種輸入隻會對應一個答案。但是，你不能重複利用這個數組中同樣的元素。

示例:

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

因為 nums[0] + nums[1] = 2 + 7 = 9
是以傳回 [0, 1]
           

https://leetcode-cn.com/problems/two-sum/

暴力方式

解題思路

思路很簡單，周遊整個數組，先找第一個值nums[i]，然後周遊找另外一個值nums[j]，兩個值相加，看看結果是不是target

代碼

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

時間複雜度O（n2）：雙層周遊，是以時間複雜度是n2

空間複雜度O（1）：沒有使用額外的空間

使用HashMap方式

解題思路

要找的是兩個數字的和，一定少不了的是數組從頭到尾的周遊，我們可以把周遊過的值都記錄下來，這樣我們就可以在周遊過的值中進行檢索了。

是以我們使用java提供的資料機構HashMap，把周遊過的值都放到HashMap中，Key為值，Value為索引。

那麼，在周遊的時候，每周遊一個值nums[i]的時候，先判斷HashMap中是否含有target-nums[i]，如果有，則直接傳回，沒有的話就繼續向下周遊，這樣我們隻需要周遊一次即可。

代碼

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

時間複雜度O（n）：數組從頭到尾周遊了一遍，是以時間複雜度為n

空間複雜度O（n）：定義了一個HashMap用來存儲周遊過的值，是以空間複雜度為n