今天晚上看了許多關于未來計算機就業的視頻，有種正被販賣焦慮的感覺，翻來覆去下決定先做一遍leetcode100給自己降降溫，打算每周做四題，盡量嘗試不同的方法與不同的語言。

一開始想到的是暴力解法，兩層循環。數據量為1e4，所以肯定能過。

class Solution {
public:vector<int> twoSum(vector<int>& nums, int target) {for(int i = 0;i<nums.size()-1;i++){for(int j = i+1;j<nums.size();j++){if(nums[i]+nums[j]==target) return {i, j};}}return {};}
};

class Solution:def twoSum(self, nums: List[int], target: int) -> List[int]:n = len(nums)for i in range(n):for j in range(i+1, n):if nums[i] + nums[j] == target:return [i, j]return []

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

時間復雜度為O(n2)，對于算法來說還是偏高了。回顧過程，最耗時間且最可能被優化的貌似是尋找值為target-nums[i]的循環，故使用哈希表。

class Solution {
public:vector<int> twoSum(vector<int>& nums, int target) {unordered_map<int, int> hashtable;for(int i = 0;i<nums.size();i++){auto it = hashtable.find(target - nums[i]);if(it != hashtable.end()){return {it->second, i};}hashtable[nums[i]] = i;}return {};}
};

class Solution:def twoSum(self, nums: List[int], target: int) -> List[int]:hashtable = dict()for i, num in enumerate(nums):if target - num in hashtable:return [hashtable[target - num], i]hashtable[nums[i]] = ireturn []

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];}
}

復雜度為O(n)

發現對于java的Map用法還是不夠熟悉，得找時間再復習一下javase了