LeetCode 前缀和+哈希表

92 阅读 0 评论 61 点赞

我是靠谱客的博主文艺皮皮虾，这篇文章主要介绍LeetCode 前缀和+哈希表，现在分享给大家，希望可以做个参考。

一、LeetCode 525 连续数组
题目描述：
给定一个二进制数组, 找到含有相同数量的 0 和 1 的最长连续子数组（的长度）。

思路：
首先把数组中是0的数，转换为-1
然后利用前缀和哈希表

代码如下：

复制代码

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
class Solution {
public:
    int findMaxLength(vector<int>& nums) {
        int res=0;
        int sum=0;
        unordered_map<int,int>mp;
        for(int& num:nums){
            if(num==0){
                num=-1;
            }
        }
        for(int i=0;i<nums.size();i++){
            sum+=nums[i];
            if(sum==0&&i>res){
                res=i+1;
            }
            if(mp.count(sum)){
                res=max(res,i-mp[sum]);
            }
            else{
                mp[sum]=i;
            }
        }
        return res;
    }
};

二、LeetCode 面试题17.05 字母与数字
题目描述：
给定一个放有字符和数字的数组，找到最长的子数组，且包含的字符和数字的个数相同。

返回该子数组，若存在多个最长子数组，返回左端点最小的。若不存在这样的数组，返回一个空数组。

思路：
把数字变成-1
把字母变成1
然后同上一题连续数组的写法

代码如下：

复制代码

class Solution {
public:
    vector<string> findLongestSubarray(vector<string>& array) {
        int n=array.size();
        vector<int>nums(n);//数字是-1，字母是1
        for(int i=0;i<n;i++){
            if(array[i][0]>='0'&&array[i][0]<='9'){
                nums[i]=-1;
            }
            else{
                nums[i]=1;
            }
        }
        int left=0,right=0;
        int res=0,sum=0;
        unordered_map<int,int>mp;
        for(int i=0;i<n;i++){
            sum+=nums[i];
            if(sum==0&&i>res){
                res=i+1;
                left=0;
                right=i;
            }
            if(mp.count(sum)){
                if(res<i-mp[sum]){
                    res=i-mp[sum];
                    left=mp[sum]+1;
                    right=i;
                }
            }
            else{
                mp[sum]=i;
            }
        }
        vector<string>ans;
        if(right<=left) return ans;
        for(int i=left;i<=right;i++){
            ans.push_back(array[i]);
        }
        return ans;
    }
};

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
class Solution {
public:
    vector<string> findLongestSubarray(vector<string>& array) {
        int n=array.size();
        vector<int>nums(n);//数字是-1，字母是1
        for(int i=0;i<n;i++){
            if(array[i][0]>='0'&&array[i][0]<='9'){
                nums[i]=-1;
            }
            else{
                nums[i]=1;
            }
        }
        int left=0,right=0;
        int res=0,sum=0;
        unordered_map<int,int>mp;
        for(int i=0;i<n;i++){
            sum+=nums[i];
            if(sum==0&&i>res){
                res=i+1;
                left=0;
                right=i;
            }
            if(mp.count(sum)){
                if(res<i-mp[sum]){
                    res=i-mp[sum];
                    left=mp[sum]+1;
                    right=i;
                }
            }
            else{
                mp[sum]=i;
            }
        }
        vector<string>ans;
        if(right<=left) return ans;
        for(int i=left;i<=right;i++){
            ans.push_back(array[i]);
        }
        return ans;
    }
};