3.哈希表与统计

3-1.最长和谐子序列：594

法一：排序+滑动窗口

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int findLHS(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int left = 0, right = 0;
        int ans = 0;
        while (left <= right && right <= nums.size() - 1) {
            if (abs(nums[right] - nums[left]) == 1) {
                ans = max(right - left + 1, ans);
                right++;
            } else if (abs(nums[right] - nums[left]) < 1) {
                right++;
            } else {
                left++;
            }
        }
        return ans;
    }
};

法二：哈希表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int findLHS(vector<int>& nums) {
        unordered_map<int, int> cnt;
        int ans = 0;
        for (int num : nums) {
            cnt[num]++;
        }
        for (auto [key, val] : cnt) {
            if (cnt.count(key + 1)) {
                ans = max(ans, val + cnt[key + 1]);
            }
        }
        return ans;
    }
};

3-2.两个数组的交集II：350

两个数组的交集:349，详见《6.0哈希表篇1-2》

法一：哈希表(最优解)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
        unordered_map<int, int> mp;
        for (int num : nums1) {
            mp[num]++;
        }
        vector<int> res;
        for (int num : nums2) {
            if (mp.count(num) && mp[num]) {
                mp[num]--;
                res.emplace_back(num);
            }
        }
        return res;
    }
};

法二：排序+双指针

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
        sort(nums1.begin(), nums1.end());
        sort(nums2.begin(), nums2.end());
        int index1 = 0, index2 = 0;
        vector<int> res;
        while (index1 < nums1.size() && index2 < nums2.size()) {
            int num1 = nums1[index1], num2 = nums2[index2];
            if (num1 == num2) {
                res.emplace_back(num1);
                index1++;
                index2++;
            } else if (num1 < num2) {
                index1++;
            } else {
                index2++;
            }
        }
        return res;
    }
};
如果${nums}_2$的元素存储在磁盘上，磁盘内存是有限的，并且你**不能一次加载所有的元素到内存中**。那么就无法高效地对${nums}_2$进行排序，因此推荐使用方法一而不是方法二。在方法一中，${nums}_2$只关系到查询操作，因此每次读取${nums}_2$中的一部分数据，并进行处理即可。

3-3.砖墙：554

哈希表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int leastBricks(vector<vector<int>>& wall) {
        unordered_map<int, int> mp;
        for (auto& widths : wall) {
            int n = widths.size();
            int sum = 0;
            for (int i = 0; i < n - 1; i++) {
                sum += widths[i];
                mp[sum]++;
            }
        }
        int maxCnt = 0;
        for (auto& [_, value] : mp) {
            maxCnt = max(maxCnt, value);
        }
        return wall.size() - maxCnt;
    }
};

3-4.在系统中查找重复文件：609

法一：哈希表

麻烦之处在于，不只是`"root/a 1.txt(abcd)"`一种格式，还可能是`"root/a 1.txt(abcd) 2.txt(efgh)"`。思路简单，但是写起来复杂。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution {
public:
    vector<vector<string>> findDuplicate(vector<string>& paths) {
        unordered_map<string, vector<string>> t;
        auto help = [](string s) -> pair<string, string> {
            string name, content;
            int i = 0;
            for(; i<s.size() && s[i] != '('; i++){
                name += s[i];
            }
            for(i++; i<s.size() && s[i] != ')'; i++){
                content += s[i];
            }
            return {name, content};
        };
        for(auto path : paths){
            string p;
            int i = 0;
            while(path[i] != ' '){
                p += path[i];
                i++;
            }
            string tmp;
            for(int l=i, r=i+1; r < path.size(); r++){
                if(path[r] == ' ' || r == path.size() - 1){
                    auto [name, content] = help(path.substr(l+1, r-l));
                    t[content].push_back(p+'/'+name);
                    l = r;
                    tmp.clear();
                }
            }
        }
        vector<vector<string>> ans;
        for(auto &[_, names] : t){
            if(names.size() > 1)
                ans.emplace_back(names);
        }
        return ans;
    }
};

法二：istringstream

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
public:
    vector<vector<string>> findDuplicate(vector<string>& paths) {
        vector<vector<string>> ans;
        unordered_map<string, vector<string>> um;   //文件内容->文件路径
        for (const string& path: paths) {
            istringstream iss(path);
            string dir, tmp;
            iss >> dir;
            while (iss >> tmp) {
                string key, val;
                getKeyAndVal(key, val, tmp, dir);
                um[key].push_back(val);
            }
        }
        for (const auto& p: um) {
            if (p.second.size() > 1) {
                ans.push_back(p.second);
            }
        }
        return ans;
    }

private:
    void getKeyAndVal(string& key, string& val, const string& tmp, const string& dir) {
        int i = 0;
        while (tmp[i] != '(') ++i;
        val = dir + "/" + tmp.substr(0, i);
        int j = i + 1;
        while (tmp[j] != ')') ++j;
        key = tmp.substr(i + 1, j - i - 1);
    }
};

关于stringstream

istringstream是继承于istream，ostringstream是继承于ostream，而他们使用的缓冲区类是stringbuf。二者详细说明：[istringstream及ostringstream超详细说明--知乎](https://zhuanlan.zhihu.com/p/367869633)


stringstream样例：[C++中stringstream样例-博客园](https://www.cnblogs.com/zhang-qc/p/9048977.html)

在这段代码中，`istringstream` 用于从字符串中提取数据。针对每个 `path`，它创建了一个 `istringstream` 对象，然后使用 `iss >> dir` 语句提取第一个字符串（目录信息），之后使用 `iss >> tmp` 循环提取后续的字符串。

优势：

  1. 方便的输入流操作：istringstream 提供了与标准输入输出流 cin 和 cout 相似的接口来处理字符串。

  2. 轻量级：istringstream 是基于内存的输入流，因此操作速度快。

  3. 可重复使用：可以重复使用 istringstream 对不同的字符串进行解析，而无需重新初始化。

  4. 数据类型转换：istringstream 提供了可以轻松将不同类型数据从字符串中提取出来的方法。

  5. 适用于分词：适用于从输入的字符串中提取单词或数据。可以使用 >> 操作符来按空格等分隔符将字符串分词。

    总之，istringstream 提供了一种方便、高效的方式来处理从字符串中提取数据，使得对文本进行解析和处理变得更加容易。在需要将字符串按照空格分割为各个部分并记录下对应值时，可以起到类似其他语言中split(' ')的作用。

3-5.四数相加II：454

💬难在思路: 分治+哈希表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
        int ans = 0;
        unordered_map<int, int> mp; //累加和->组合数
        for (int& a : nums1) {
            for (int& b : nums2) {
                mp[a + b]++;
            }
        }
        for (int& c : nums3) {
            for (int& d : nums4) {
                if (mp.count(-c - d)) {
                    ans += mp[-c - d]; // 不能只加一次，可能多种情况
                    // 同时不应再改变mp[-c-d]的值
                }
            }
        }
        return ans;
    }
};
三数之和：15,四数之和：18。这两题最优解为双指针，而不是哈希表。有时候哈希表时空开销太大时，双指针往往能很好地解决。

3-6.多数元素：169

法一：哈希表(27ms,27.3MB)✅

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int majorityElement(vector<int>& nums) {
        unordered_map<int, int> counts;
        int majority = 0, cnt = 0;
        for (int num : nums) {
            ++counts[num];
            if (counts[num] > cnt) {
                majority = num;
                cnt = counts[num];
            }
        }
        return majority;
    }
};

法二：排序+取众数(20ms,27.2MB)

这里的”多数元素”出现次数超过总次数的一半，所以必定是众数，并且排序后位于中间的数一定是众数（数学思维）。

1
2
3
4
5
6
7
class Solution {
public:
    int majorityElement(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        return nums[nums.size() / 2];
    }
};

虽然时间复杂度比法一高，但实际运行时间会更小。使用堆排序可以进一步减小空间开销。

法三：随机数(了解)

最坏时间复杂度为$O(\infty)$，可能一直找不到众数。用rand()生成随机数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int majorityElement(vector<int>& nums) {
        while (true) {
            int candidate = nums[rand() % nums.size()];
            int count = 0;
            for (int num : nums)
                if (num == candidate)
                    ++count;
            if (count > nums.size() / 2)
                return candidate;
        }
        return -1;
    }
};

法四：分治(24ms,26MB)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
    int count_in_range(vector<int>& nums, int target, int lo, int hi) {
        int count = 0;
        for (int i = lo; i <= hi; ++i)
            if (nums[i] == target)
                ++count;
        return count;
    }
    int majority_element_rec(vector<int>& nums, int lo, int hi) {
        if (lo == hi)
            return nums[lo];
        int mid = (lo + hi) / 2;
        int left_majority = majority_element_rec(nums, lo, mid);
        int right_majority = majority_element_rec(nums, mid + 1, hi);
        if (count_in_range(nums, left_majority, lo, hi) > (hi - lo + 1) / 2)
            return left_majority;
        if (count_in_range(nums, right_majority, lo, hi) > (hi - lo + 1) / 2)
            return right_majority;
        return -1;
    }
public:
    int majorityElement(vector<int>& nums) {
        return majority_element_rec(nums, 0, nums.size() - 1);
    }
};

法五：Boyer-Moore投票算法(17ms,26.1MB)✅

详见本题摩尔投票清晰图解。核心思想为对拼消耗，如果元素出现次数不超过一半，则该方法失效，这时候就需要用到其泛化版———Misra-Gries算法。

如何理解摩尔投票算法？—力扣

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int x = 0, votes = 0;
        for (int num : nums){
            if (votes == 0) x = num;
            votes += num == x ? 1 : -1;
        }
        return x;
    }
};

拓展.多数元素II：229

法一：哈希表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    vector<int> majorityElement(vector<int>& nums) {
        unordered_map<int, int> counts;
        vector<int> ans;
        int n = nums.size();
        for (auto& num : nums) {
            counts[num]++;
        }
        for (auto& cnt : counts) {
            if (cnt.second > n / 3) {
                ans.push_back(cnt.first);
            }
        }
        return ans;
    }
};

法二：摩尔投票法✅

出现次数超过$\lfloor\frac{n}{2}\rfloor$的最多只能有一个，出现次数超过$\lfloor\frac{n}{3}\rfloor$的最多只能有两个。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
class Solution {
public:
    vector<int> majorityElement(vector<int>& nums) {
        vector<int> ans;
        int n = nums.size();
        // 临时元素1和2，对应投票votes1和votes2
        int element1 = 0, element2 = 0, votes1 = 0, votes2 = 0;
        for (auto& num : nums) {
            if (votes1 > 0 && num == element1) {
                // 如果该元素为第一个元素，则计数加1
                votes1++;
            } else if (votes2 && num == element2) {
                // 如果该元素为第二个元素，则计数加1
                votes2++;
            } else if (votes1 == 0) {
                // 选择第一个元素
                element1 = num;
                votes1++;
            } else if (votes2 == 0) {
                // 选择第二个元素
                element2 = num;
                votes2++;
            } else {
                // 如果三个元素均不相同，则相互抵消1次
                votes1--;
                votes2--;
            }
        }

        int cnt1 = 0, cnt2 = 0;
        for (auto& num : nums) {
            if (votes1 > 0 && num == element1) {
                cnt1++;
            }
            if (votes2 > 0 && num == element2) {
                cnt2++;
            }
        }
        // 检测元素出现的次数是否满足要求,因为不一定是存在两个数
        if (votes1 > 0 && cnt1 > n / 3) {
            ans.push_back(element1);
        }
        if (votes2 > 0 && cnt2 > n / 3) {
            ans.push_back(element2);
        }
        return ans;
    }
};

同理，可以使用该代码解决$\lfloor\frac{n}{m}\rfloor$的情况，只需要让备选element和votes的数目为$m-1$即可。

4.哈希表与前缀和(难理解)

前缀思想推荐文章【动画模拟】一文秒杀七道题—力扣（LeetCode）,包括前缀和/奇数/积…

4-1.和为K的子数组：560

法一：枚举(超时)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        int ans = 0;
        for (int right = 0; right < nums.size(); right++) {
            int sum = 0;
            for (int left = right; left >= 0; left--) {
                sum += nums[left];
                if (sum == k) {
                    ans++;
                }
            }
        }
        return ans;
    }
};

该题用滑动窗口难以实现，因为存在负数。比如[-2,-1,0,1,2]，k=0。单纯的滑动窗口会使得漏掉[-1,0,1]。转而用动态规划，又容易导致内存溢出。

法二：前缀和+哈希表优化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        unordered_map<int, int> mp;//前缀和，出现次数
        mp[0] = 1;
        int pre = 0, ans = 0; // pre记录前缀和
        for (auto& num : nums) {
            pre += num;
            if (mp.find(pre - k) != mp.end()) {
                ans += mp[pre - k];
            }
            mp[pre]++;
        }
        return ans;
    }
};

推导和图解详见官方题解。

4-2.连续的子数组和：523

前缀和＋哈希表,本题综合性较强。

详细解答【宫水三叶】拓展到求方案数问题—LeetCode

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    bool checkSubarraySum(vector<int>& nums, int k) {
        int n = nums.size();
        if (n < 2) {
            return false;
        }
        unordered_map<int, int> mp;//<前缀和%k,索引>
        mp[0] = -1;//因为元素均为非负数，所以前缀和不可能为0，即对应索引为-1无效值
        int presum = 0;
        for (int i = 0; i < n; i++) {
            presum = (presum + nums[i]) % k;
            if (mp.count(presum)) {
                int preIdx = mp[presum];
                if (i - preIdx >= 2) {//子数组长度至少为2
                    return true;
                }
            } else {
                mp[presum] = i;//注意记录的是索引而不是次数，因为需要比较i-preIdx是否>=2
            }
        }
        return false;
    }
};

拓展：如果说还要记录下子数组长度，可以使用unordered_map<int,pair<int,int>>mp;//<前缀和%k,pair<索引，长度>>。

4-3.连续数组：525

前缀和+哈希表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    int findMaxLength(vector<int>& nums) {
        int n = nums.size();
        unordered_map<int, int> mp;
        mp[0] = -1;                 // 记录索引而非次数
        int presum = 0, maxLen = 0; // presum记录0/1交替的长度
        for (int i = 0; i < n; i++) {
            // 在这里可以将1视作1,0视作-1，交替的和就是presum前缀和
            if (nums[i]) {
                presum++;
            } else {
                presum--;
            }
            // 问题转化为：如何求得最长一段区间和为0的子数组,所以这里的k==0
            if (mp.count(presum)) {
                int preIdx = mp[presum];
                maxLen = max(maxLen, i - preIdx);
            } else {
                mp[presum] = i;
            }
        }
        return maxLen;
    }
};