Day20260303#

最长连续序列#

给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。

请你设计并实现时间复杂度为 O(n) 的算法解决此问题。

题解#

本题的难度主要在于要用O(n)的方法解决问题。采用的是哈希表的方法。首先用一个hash表记录存在的数值,采用一个<int,bool>的一个哈希表。然后遍历这个哈希表的key,我们要从最小的遍历，即如果key-1 在这个哈希表中，我们那么key一定会被key-1遍历到，所以我们只需要考虑，key-1 不在hash表中的key,然后再遍历，直到key+n不在hash表中。

1
class Solution {
2
public:
3
    int longestConsecutive(vector<int>& nums) {
4

5
        unordered_map<int,int> ump;
6

7
        for(int i=0;i<nums.size();i++){
8
            ump[nums[i]] = 1;
9
        }
10
        int ans = 0;
11
        for(auto val:ump){
12
            if(ump.find(val.first-1) != ump.end()) continue;
13
            int tmp = 0;
14
            int tmpNum = val.first;
15
            while(ump.find(tmpNum) != ump.end()){
16
                tmpNum++;
17
                tmp++;
18
            }
19

20
            ans = max(ans,tmp);
21
        }
22

23
        return ans;
24

25

26
    }
27
};

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

给定两个字符串 s 和 p，找到 s 中所有 p 的异位词的子串，返回这些子串的起始索引。不考虑答案输出的顺序。

解答#

最容易想到的解法就是完全暴力法，对s中的每个字母，向后截取p个字符，然后看这p个字符是否与p为异位词。复杂度为O(spplog(p)) 。这里判断异位词的方法是排序后判断，我们也可以优化为用一个桶来记录，因为字符就只有26个。然后我们复杂度就被优化为一个O(sp*26)。

然后考虑到对于s的每个字串的桶似乎是有关系的,不需要每个字串都创建一个新的桶，就是把上一个桶的进行部分加减就得到了下个桶，这里复杂度就被优化成了O(s*26)

当然还可以继续优化，这里每次我们都要比较p的桶与s字串的桶，因此会有一个26的较大的常数。为了优化这个常数，我们可以把这两个桶合并为一个桶，p的就是负的，s的字串就是正的，然后维护一个int 类型的diff变量，变量初始化为桶里面每个值的绝对值。然后窗口滑动时再根据逻辑对diff进行加减，最终复杂度也还是O(s)

1
class Solution {
2
public:
3

4
    vector<int> findAnagrams(string s, string p) {
5
        int sLen = s.size();
6
        int pLen = p.size();
7
        if(sLen < pLen) return vector<int>(0);
8

9
        vector<int> count(26);
10
        vector<int> ans;
11
        int differ = 0;
12

13
        for(int i=0;i<pLen;i++){
14
            count[s[i] - 'a']++;
15
            count[p[i] - 'a']--;
16
        }
17

18

19

20
        for(int i=0;i<26;i++){
21
           differ += abs(count[i]);
22
        }
23

24
        if(differ==0) ans.push_back(0);
25

26
        for(int i=pLen;i<sLen;i++){
27
            if(count[s[i]-'a'] < 0){
28
                differ--;
29
            }else{
30
                differ++;
31
            }
32
            count[s[i]-'a']++;
33

34
            if(count[s[i-pLen]-'a'] > 0){
35
                differ--;
36
            }else{
37
                differ++;
38
            }
39
            count[s[i-pLen]-'a']--;
40
            if(differ==0){
41
                ans.push_back(i-pLen+1);
42
            }
43
        }
44

45
        return ans;
46

47
    }
48
};

和为k的子数组#

给你一个整数数组 nums 和一个整数 k ，请你统计并返回该数组中和为 k 的子数组的个数。

子数组是数组中元素的连续非空序列。

解答#

关键在于子数组，连续的一堆值因此考虑前缀和。如果求出前缀和数组pre 。对任意pre[i] 我们要考虑的就是找出pre数组中是否存在pre[i] - k的值，且这个值必须在i之前出现，出现多少次就会有多少个满足条件的数组。到这里就能联想的两数之和的思路，采用哈希表优化。从左到右初始化哈希表，因为我们考虑的始终是i左侧的数。

1
lass Solution {
2
public:
3
    int subarraySum(vector<int>& nums, int k) {
4
        int len = nums.size();
5
        int ans=0;
6
        vector<int> pre(len+1);
7
        pre[0] = 0;
8
        for(int i=1;i<=len;i++){
9
            pre[i] = pre[i-1] + nums[i-1];
10
        }
11

12
        unordered_map<int,int> record;
13

14
        for(int i=0;i<=len;i++){
15
            int target = pre[i] - k;
16
            if(record.find(target) != record.end()){
17
                ans += record[target];
18
            }
19

20
            if(record.find(pre[i]) != record.end()){
21
                record[pre[i]] ++;
22
            }else{
23
                record[pre[i]] = 1;
24
            }
25
        }
26

27

28
        return ans;
29
    }
30
};