今天晚上看了许多关于未来计算机就业的视频，有种正被贩卖焦虑的感觉，翻来覆去下决定先做一遍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(n²)，对于算法来说还是偏高了。回顾过程，最耗时间且最可能被优化的貌似是寻找值为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了