使用哈希表,C++编写可A代码

最长的可整合子数组的长度

http://www.nowcoder.com/questionTerminal/677a21987e5d46f1a62cded9509a94f2

使用语言:C++
时间复杂度:图片说明
空间复杂度:图片说明

解题思路:
可以先从数组的性质下手,对于一个排好序的数组,如果要让数组中每个相邻元素的差都为1,那么数组的长度一定会等于数组中最大值与最小值的差值。
反过来推导,如果数组的长度等于数组中最大值与最小值的差值,就只有两种情况:
1、数组中存在相等的元素,比如:[2, 3, 4, 4, 6, 7]
2、满足题目需求,数组中每个相邻元素的差都为1,比如:[2, 3, 4, 5, 6]

(可能有些小伙伴会想有没有可能存在第三种可能,假如中间存在两相邻的数之差大于1,比如:[2, 4, 5, 6],但很容易证明这时 最大值与最小值的差值 != 数组长度

所以我们只要排除掉第一种情况,剩下的就是满足题目需求的子数组,而对于查找重复元素的问题,我们首先就会想到哈希表,说到这应该大家都会了吧~

注意:子数组是连续的,且不打乱原数组的排列顺序

代码:

#include <bits/stdc++.h>
using namespace std;

int fun(vector<int>& arr, int n) {
    if(n <= 1)
        return n;

    int res = 1;
    unordered_set<int> nums;

    for(int i = 0; i < n; i ++){
        int max_val = 0, min_val = INT_MAX;
        for(int j = i; j < n; j ++){
            if(nums.find(arr[j])!=nums.end()) // 排除子数组中有重复元素的情况
                break;
            nums.insert(arr[j]);
            // 检测子数组中的最大值与最小值
            max_val = max(max_val, arr[j]);
            min_val = min(min_val, arr[j]);
            // 当最大值与最小值的差等于子数组的长度时,表示子数组中每个数都是相差1
            if(max_val - min_val == j - i)
                res = max(res, j - i + 1);
        }
        nums.clear();
    }
    return res;
}

int main(){
    int n;
    cin>>n;
    vector<int> arr(n);
    for(int i=0;i<n;i++)
        cin>>arr[i];

    cout << fun(arr, n) << endl;
    return 0;
}
全部评论

相关推荐

头像
05-12 09:14
点赞 评论 收藏
转发
2 收藏 评论
分享
牛客网
牛客企业服务