LeetCode100.1 两数之和

今天晚上看了许多关于未来计算机就业的视频，有种正被贩卖焦虑的感觉，翻来覆去下决定先做一遍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]] = i
        return []

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了