【LeetCode 热题 100】哈希、双指针、滑动窗口

_小羊_

发布于 2025-04-22 01:00:24

12200

代码可运行

文章被收录于专栏：C++C++

运行总次数：0

代码可运行

LeetCode 热题 100 中大多数题我都在算法专栏中写过解题思路，本篇的存在是为了记录一下刷这些明星题的过程（不记录一下总感觉白刷了🤡），因此题解不是很多（虽然你清楚的知道真正原因是什么），望见谅。

哈希

两数之和

两数之和

遍历数组，对于当前 nums[i]，查哈希表是否存在 target - nums[i]，如果存在返回两个数对应的下标，如果不存在则哈希表存储数组元素和其对应的下标。

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

字母异位词分组

字母异位词分组

遍历字符串数组，得到一个字符串后排序其备份，用哈希表分类存储排序后相同的字符串，最后得到字符串和字符串数组的映射，其中 hash.second 就是我们想要的结果。

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string, vector<string>> hash;
        for (auto& s : strs)
        {
            string tmp = s;
            sort(tmp.begin(), tmp.end());
            hash[tmp].push_back(s);
        }
        vector<vector<string>> ret;
        for (auto& e : hash)
        {
            ret.push_back(e.second);
        }
        return ret;
    }
};

最长连续序列

最长连续序列

用哈希表存储所有数字，遍历哈希表，找到一段数字连续的左边界，统计右边一共有多长，遍历完哈希表就能找到最长的数字连续序列。

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        unordered_set<int> hash;
        for (auto e : nums) hash.insert(e); // 先将所有数字存起来
        int maxlen = 0;
        for (auto e : hash)
        {
            if (!hash.count(e - 1)) // 找到一段连续的左边界
            {
                int len = 1;
                while (hash.count(e + 1)) // 统计右边有多长
                {
                    len++;
                    e++;
                }
                maxlen = max(maxlen, len); // 得出最长长度
            }
        }
        return maxlen;
    }
};

双指针

移动零

移动零

让左指针始终指向0，右指针向右遍历数组找非0，找到一个就和左指针交换，这样就可以把0不断推到数组后面。

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int l = 0, r = 0;
        while (r < nums.size())
        {
            if (nums[r]) swap(nums[l++], nums[r]);
            r++;
        }
    }
};

盛最多水的容器

盛最多水的容器

当以较小的这条边为基准，另一边不断收缩时，容器宽度不断减小，高度不管怎么样也是不会比当前高度高的，因为容器的高度取决于较小的一条边，所以这条较小的边就不需要作为基准遍历的了。

class Solution {
public:
    int maxArea(vector<int>& height) {
        int ret = 0;
        for (int l = 0, r = height.size() - 1; l < r;)
        {
            ret = max(ret, (r - l) * min(height[l], height[r]));
            if (height[l] < height[r]) l++;
            else r--;
        }
        return ret;
    }
};

三数之和

三数之和

先对数组进行排序，从左向右或从右向左依次固定一个数，在另一边固定两个指针不断收缩遍历，当三个指针指向的值满足要求时加入到结果中。

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        vector<vector<int>> ret;
        int n = nums.size() - 1; // 固定一个位置
        while (n > 1)
        {
            int l = 0, r = n - 1, target = -nums[n];
            if (target > 0) break;
            while (l < r)
            {
                int sum = nums[l] + nums[r];
                if (sum < target) l++;
                else if (sum > target) r--;
                else
                {
                    ret.push_back({nums[l], nums[r], -target});
                    l++, r--;
                    while (l < r && nums[l] == nums[l - 1]) l++;
                    while (l < r && nums[r] == nums[r + 1]) r--;
                }
            }
            n--;
            while (n > 1 && nums[n] == nums[n + 1]) n--;
        }
        return ret;
    }
};

接雨水

接雨水

从左右两边向中间遍历，假设中间没有柱子，记录最小高度min_h，当前最小高度h，则雨水体积为 v = (h - min_h) * (r - l)，然后从小的一边收缩，当遇到柱子时减去该柱子高度和记录的最小高度差值中的较小值。

class Solution {
public:
    int trap(vector<int>& height) {
        int l = 0, r = height.size() - 1;
        int v = 0, min_h = 0;
        while (l < r)
        {
            int h = min(height[l], height[r]);
            if (h > min_h)
            {
                v += (r - l) * (h - min_h);
                min_h = h;
            }
            if (height[l] < height[r]) v -= min(height[l++], min_h);
            else v-= min(height[r--], min_h);
        }
        return v;
    }
};

官方题解：

双指针从两边向中间遍历，过程中分别记录左边和右边最大值，哪边小哪边收缩，此刻收缩的这边暂时能接到的雨水为 max_r - height[r] 或 max_l - height[l]。

class Solution {
public:
    int trap(vector<int>& height) {
        int l = 0, r = height.size() - 1;
        int v = 0, max_l = 0, max_r = 0;
        while (l < r)
        {
            max_l = max(max_l, height[l]);
            max_r = max(max_r, height[r]);
            if (height[l] < height[r]) v += max_l - height[l++];
            else v += max_r - height[r--];
        }
        return v;
    }
};

滑动窗口

无重复字符的最长子串

无重复字符的最长子串

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        unordered_set<char> set;
        int l = 0, r = 0, res = 0;
        while (r < s.size())
        {
            while (set.count(s[r])) set.erase(s[l++]);
            res = max(res, r - l + 1);
            set.insert(s[r++]);
        }
        return res;
    }
};

找到字符串中所有字母异位词

找到字符串中所有字母异位词

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        int n = p.size();
        int hash1[26] = {};
        for (auto ch : p) hash1[ch - 'a']++;
        int hash2[26] = {};
        vector<int> res;
        for (int l = 0, r = 0, cnt = 0; r < s.size(); r++)
        {
            int in = s[r] - 'a';
            if (++hash2[in] <= hash1[in]) cnt++;
            while (r - l + 1 > n)
            {
                int out = s[l++] - 'a';
                if (hash2[out]-- <= hash1[out]) cnt--;
            } 
            if (cnt == n) res.push_back(l);
        }
        return res;
    }
};