题解 | #子群的标签和# 哈希表

知识点

哈希表 set

思路

对于连续子数组的和我们可以拆分成两段前缀和的差。因此从前向后遍历，一边维护前缀和，一边用哈希表记录每个前缀和对应的末尾元素的位置，特别的开头一段可以认为用一个空数组，末尾位置是-1。

要注意必须维护全部的下标而不是最后一个下标，因为如果存在某一段的和为0，那么每次遍历一个末尾就可能有多个子数组被加入答案。

比如这个：

[1,2,-2,1], 1

题目要求答案去重有序，可以用一个set来维护，最后返回答案。

时间复杂度

很迷惑，n可以达到3e5，虽然不太好确定结果的数组中长度是多少，但是n这个级别一定是有的，再加上复制数组的时间可以达到 $O(n^2)$ ，用set维护至少还有 $O(logn)$ 级别，总体时间复杂度可达 $O(n^2logn)$ 一定是过不去的，可能存在更优秀的解法吧

数据出来背锅！！

AC Code（C++）

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @param k int整型 
     * @return int整型vector<vector<>>
     */
    vector<vector<int> > subarraySum(vector<int>& nums, int k) {
        unordered_map<int, vector<int>> mp;
        mp[0].push_back(-1);
        int sum = 0;
        set<vector<int>> S;
        for (int i = 0; i < nums.size(); i ++) {
            sum += nums[i];
            for (auto last : mp[sum - k]) {
                S.insert(vector<int>(nums.begin() + last + 1, nums.begin() + i + 1));
            }
            mp[sum].push_back(i);
        }
        return vector<vector<int>>(S.begin(), S.end());
    }
};