twoSum

起因:coding能力太差导致期末考试被制裁

因此

今天从LeetCode的第一题两数之和开始数据结构与算法的学习

首先给出题目

第一个想法是直接两层for循环暴力枚举所有可能

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

虽然空间复杂度为O(1)，但是这样的话引入了很多无意义比较，比如某个nums[i]可能很小，却和很多不可能匹配的数相加，浪费了许多时间，因此时间复杂度达到了$O(n^2)$，太低效了…

看看能不能尝试优化一下，减少无意义的搜索

可以想到先对其进行排序，然后用左右双指针法根据两数之和与target的大小关系移动指针，使其更高效

代码如下

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector <pair<int, int>> a;
        for(int i = 0; i < nums.size(); i++){
            a.push_back({nums[i],i});
        }
        sort(a.begin(),a.end());

        int l = 0, r = a.size() - 1;
        while(l < r){
            int sum = a[l].first + a[r].first;
            if(sum == target){
                return {a[l].second,a[r].second};
            }else if(sum < target){
                l++;
            }else{
                r--;
            }
        }
        return {};
    }
};

此时空间复杂度是O(n)

可以看到确实快了一些，但是还不够，排序的时间复杂度为$O(n \log n)$，能不能不排序，直接实现快速查找？

这便要引出今天的数据结构:哈希表

我们对题目再重新思考一下，题目其实在问，对于每个数x，是否存在一个数y = target - x？

这本质其实是一个查找问题，而不是枚举问题

我们可以这样做…

先遍历数组，对当前nums[i]计算need = target - nums[i]，如果need已经出现过，那么直接返回，否则就把 nums[i]存进哈希表

这样时间复杂度便能达到O(n)，甚至是O(1)！

代码如下

#include <unordered_map>
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map <int, int> mp; //值，索引
        for(int i = 0; i < nums.size(); i++){
            int need = target - nums[i];
            if(mp.count(need)){
                return {mp[need],i};
            }else{
                mp[nums[i]] = i;
            }
        }
        return {};
    }
};

时间复杂度完美，空间复杂度仍然是O(n)，因为哈希表本质就是空间换时间(不绝对)

待补充…

2026.1.19

仅记录一下做过的题目的代码…

49.字母异位词分组

解法:

哈希表

我们通过对字符串字符排序，将字母组成相同的字符串映射到同一个键，从而利用哈希表实现异位词分组~

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string, vector<string>> mp;

        for(string s : strs) {
            string key =  s;
            sort(key.begin(),key.end()); //排序
            mp[key].push_back(s); //值，索引
        }

        vector<vector<string>> result;

        for(auto& p : mp){
            result.push_back(p.second);
        }
        return result;
    }
};

128.最长连续序列

解法:

哈希表

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        unordered_set<int> st(nums.begin(), nums.end());
        int ans = 0;
        //思考...
        for (int x : st) {
            if (!st.count(x - 1)) {
                int cur = x;
                int len = 1;

                while (st.count(cur + 1)) {
                    cur++;
                    len++;
                }
                ans = max(ans, len); //举一反三
            }
        }
        return ans;
    }
};

注意一下unordered_map和unordered_set的区别

unordered_set只有key(只关心元素存不存在)，unordered_map存在key->value的映射关系

哈希表的底层原理:

桶数组(bucket array) + 哈希函数(映射关系) + 链表/树?(处理哈希冲突) + 负载因子扩容(rehash)

待补充…

2026.2.11吐槽:

最近尝试用cpp手搓一个stl

被cpp的逆天语法击败了

怎么会有这么抽象的语言???

后面写到 map set unordered_map unordered_set 再说

我才知道这些的底层原理原来还不一样qwq

还好之前写过红黑树，在密码学中也接触过hash~

拜拜~