1. 两数之和

不妨设 i < j i<j i<j 且 n u m s [ i ] + n u m s [ j ] = t a r g e t nums[i]+nums[j]=target nums[i]+nums[j]=target，于是有 n u m s [ i ] = t a r g e t − n u m s [ j ] nums[i]=target-nums[j] nums[i]=target−nums[j]。我们只需要枚举 n u m s [ j ] nums[j] nums[j]，然后看 n u m s [ j ] nums[j] nums[j] 的前面是否存在元素 t a r g e t − n u m s [ j ] target-nums[j] target−nums[j] 即可，这可以用一个哈希表来记录。

1.1 C++实现

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

1.2 Python实现

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        idx = {}
        for i in range(len(nums)):
            if target - nums[i] in idx:
                return [idx[target - nums[i]], i]
            else:
                idx[nums[i]] = i
        return []

1.3 时空分析

n n n 是 n u m s nums nums 的元素数量。

时间复杂度： O ( n ) O(n) O(n)。因为要遍历一次。
空间复杂度： O ( n ) O(n) O(n)。哈希表的大小。

2. 字母异位词分组

注意到字母异位词按照字典序排列后等于原单词，因此我们可以以原单词为键来记录该单词衍生出的所有字母异位词。

2.1 C++实现

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string, vector<string>> mp;
        for (auto& str: strs) {
            string key = str;
            sort(key.begin(), key.end());
            mp[key].push_back(str);
        }

        vector<vector<string>> ans;
        for (auto& [k, v]: mp) ans.push_back(v);

        return ans;
    }
};

2.2 Python实现

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        mp = collections.defaultdict(list)
        for s in strs:
            mp[''.join(sorted(s))].append(s)
        return list(mp.values())

2.3 时空分析

n n n 是 s t r s strs strs 中的字符串数量， k k k 是这 n n n 个字符串的最大长度。

时间复杂度： O ( n k log ⁡ k ) O(nk\log k) O(nklogk)。因为要遍历 n n n 个字符串并对每个字符串花 O ( k log ⁡ k ) O(k\log k) O(klogk) 的时间进行排序。
空间复杂度： O ( n k ) O(nk) O(nk)。需要用哈希表存储所有的字符串。

3. 最长连续序列

题目要求在 O ( n ) O(n) O(n) 的时间内完成，所以我们不能对原数组进行排序。

考虑枚举数组中的每个数 x x x，以它为起点，尝试匹配 x + 1 , x + 2 , ⋯ x+1,x+2,\cdots x+1,x+2,⋯ 直到 x + y x+y x+y，那么此时以 x x x 为起点的最长连续序列的长度为 y + 1 y+1 y+1。

3.1 C++实现

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        if (nums.empty()) return 0;

        unordered_set<int> mp;
        for (auto& num: nums) mp.insert(num);

        int ans = 0;
        for (auto& num: nums) {
            if (!mp.count(num - 1)) {
                int curlen = 1, curnum = num;
                while (mp.count(curnum + 1)) {
                    curlen++, curnum++;
                }
                ans = max(ans, curlen);
            }
        }

        return ans;
    }
};

3.2 Python实现

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        if not nums: return 0

        mp = set(nums)
        ans = 0

        for num in nums:
            if num - 1 not in mp:
                curlen, curnum = 1, num
                while curnum + 1 in mp:
                    curlen += 1
                    curnum += 1
                ans = max(ans, curlen)

        return ans

3.3 时空分析

n n n 是 n u m s nums nums 的长度。

时间复杂度： O ( n ) O(n) O(n)。因为要遍历一次。
空间复杂度： O ( n ) O(n) O(n)。哈希表的大小。

péripatéticien

【2023】LeetCode HOT 100——哈希

目录