【小Y學演算法】??每日LeetCode打卡??—

🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻
🌲 從今天起，每天打卡一道演算法題，既是一個學習程序，又是一個分享的程序😜
🌲 提示：本專欄解題編程語言一律使用 C# 和 Java 兩種進行解題
🌲 要保持一個每天都在學習的狀態，讓我們一起努力成為演算法大神吧🧐！
🌲 今天是力扣演算法題持續打卡第1天🎈！
🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻

🌲原題樣例

題目：

給定一個整數陣列 nums 和一個整數目標值 target，請你在該陣列中找出和為目標值 target 的那兩個整數，并回傳它們的陣列下標，
你可以假設每種輸入只會對應一個答案，但是，陣列中同一個元素在答案里不能重復出現，
你可以按任意順序回傳答案，

示例 1：
輸入：nums = [2,7,11,15], target = 9 輸出：[0,1]
解釋：因為 nums[0] + nums[1] ==
9 ，回傳 [0, 1] ，

示例 2：
輸入：nums = [3,2,4], target = 6
輸出：[1,2]

示例 3：
輸入：nums = [3,3], target = 6
輸出：[0,1]

提示：

2 <= nums.length <= 104
-109 <= nums[i] <= 109
-109 <= target <= 109
只會存在一個有效答案

🌞解題思路

🌻C#方法一：暴力法

看了題目，很自然的就會想到，只要進行兩層回圈，對所有的數字進行一次相加，當和為target時，將兩個值的index回傳即可

    //方法一：
    public int[] TwoSum(int[] nums, int target)
    {
        for (int i = 0; i < nums.Length; i++)
        {
            for (int j = i + 1; j < nums.Length; j++)
            {
                if (nums[i] + nums[j] == target)
                {
                    return new int[] { i, j };
                }
            }
        }
        return new int[] { 0, 0 };
    }

執行結果
執行結果通過，執行用時 480ms，記憶體消耗 29.6MB .

復雜度分析
時間復雜度： O(n^2)
空間復雜度： O(1)

🌻C#方法二：哈希

解法：采用哈希表，節省遍歷時間
詳細：通過鍵值對保存陣列值與索引的關系，在之后的尋值（找target-nums[i]）時可以一步尋到，省去再次遍歷陣列的時間，

public class Solution {
//方法二
    public int[] TwoSum(int[] nums, int target) {
        int[] result = new int[2];
            Dictionary<int, int> dic = new Dictionary<int, int>();
            for (int i = 0; i < nums.Length; i++) {
                if (dic.ContainsKey(nums[i]))
                {
                    dic[nums[i]] += 1;
                }
                else {
                    dic[nums[i]] = 0;
                }
            }
            for (int i = 0; i < nums.Length; i++)
            {
                if (nums.Contains(target - nums[i]))
                {
                    result[0] = i;
                    result[1] = nums.ToList().FindIndex(item => item == target - nums[i]);
                    if (result[0] != result[1]) { break; }
                }
            }
        return result;
    }
}

執行結果
執行用時: 272 ms；記憶體消耗: 32.4 MB

🎋Java方法一：暴力列舉

思路及演算法

最容易想到的方法是列舉陣列中的每一個數 x，尋找陣列中是否存在 target - x，

當我們使用遍歷整個陣列的方式尋找 target - x 時，需要注意到每一個位于 x 之前的元素都已經和 x 匹配過，因此不需要再進行匹配，而每一個元素不能被使用兩次，所以我們只需要在 x 后面的元素中尋找 target - x，

代碼

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

執行結果
執行用時：51 ms ; 記憶體消耗：38.6 MB

復雜度分析
時間復雜度：O(N^2)O(N 2)，其中 NN 是陣列中的元素數量，最壞情況下陣列中任意兩個數都要被匹配一次，
空間復雜度：O(1)O(1)，

🎋Java方法二：哈希表

思路及演算法

注意到方法一的時間復雜度較高的原因是尋找 target - x 的時間復雜度過高，因此，我們需要一種更優秀的方法，能夠快速尋找陣列中是否存在目標元素，如果存在，我們需要找出它的索引，

使用哈希表，可以將尋找 target - x 的時間復雜度降低到從 O(N)O(N) 降低到 O(1)O(1)，

這樣我們創建一個哈希表，對于每一個 x，我們首先查詢哈希表中是否存在 target - x，然后將 x 插入到哈希表中，即可保證不會讓 x 和自己匹配，

代碼

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