微众银行秋招笔试真题解析

大家好，我是吴师兄，关注我，每周更新大厂最新笔试题解析。

题目描述

小美想要买糖果店的一根长长的糖果，糖果店顾客可以从中选取一个位置然后老板会在那切断，糖果前端到那个切断位置的糖果就会出售给这位顾客。这个糖果其实不同段有着不同的口味，小美希望她选出来的糖果中各个段有着不同的口味，在这基础上希望能选出尽可能长的糖果。小美想知道她能买到最长多长的糖果，请你帮帮她。

输入描述

第一行1个整数n，表示糖果的长度。

第二行n个整数a1 a2 ... an，其中ai表示从糖果前端开始第i段的口味，每段均1为单位长度。

对于100%的数据，1<=n<=50000，1<=ai<=50000

输出描述

输出一行一个整数表示能买到的糖果的最长长度，且其中不包含相同口味.

示例一

输入

5
1 2 3 3 4

输出

3

说明

如果我们买长度为4的糖果，包含的口味为[1,2,3,3]，存在了重复。

而长度为3时，包含的口味为[1,2,3]，不存在重复。因此长度3为最长的不存在重复口味糖果长度。

解题思路

题目乍一看是LeetCode3、无重复字符的最长子串原题，但要注意审题和题目场景，还挺坑的。

题目要求只能从糖果的前端出发开始切一刀，所以无需进行滑窗，只需要判断从起始位置开始的最长无重复子数组即可，故直接使用哈希集合即可完成。

代码

# 题目：【哈希集合】微众银行2023秋招-切糖果
# 作者：闭着眼睛学数理化
# 算法：哈希集合
# 代码有看不懂的地方请直接在群上提问


n = int(input())
nums = list(map(int, input().split()))
hash_set = set()
# 遍历数组nums中的每一个元素num
for num in nums:
    # 若num从未出现过，则加入哈希集合中
    if num not in hash_set:
        hash_set.add(num)
    # 若num出现过，则直接退出循环
    else:
        break

# 退出循环后，哈希集合的长度即为答案
print(len(hash_set))

Java

import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) {
            nums[i] = scanner.nextInt();
        }
        
        Set<Integer> hashSet = new HashSet<>();
        
        int count = 0;
        for (int num : nums) {
            if (!hashSet.contains(num)) {
                hashSet.add(num);
                count++;
            } else {
                break;
            }
        }
        
        System.out.println(count);
    }
}

C++

#include <iostream>
#include <unordered_set>
#include <vector>

using namespace std;

int main() {
    int n;
    cin >> n;
    
    vector<int> nums(n);
    for (int i = 0; i < n; i++) {
        cin >> nums[i];
    }
    
    unordered_set<int> hashSet;
    
    int count = 0;
    for (int num : nums) {
        if (hashSet.find(num) == hashSet.end()) {
            hashSet.insert(num);
            count++;
        } else {
            break;
        }
    }
    
    cout << count << endl;
    
    return 0;
}

时空复杂度

时间复杂度：O(N)。最差的情况是遍历整个数组。

空间复杂度：O(N)。哈希集合所需空间。

小结

不知道怎么样开始刷 LeetCode ，那么可以参考我整理的这个刷题路线，历时两年，经历了上千个同学的实操检验。

LeetCode 刷题顺序，看这一篇就够了

看了很多算法视频、参加了很多算法训练营，还是感觉很难入门，那么可以尝试看动画刷 LeetCode 。

看动画刷 LeetCode

刷了很多 LeetCode ，面对大厂的算法真题却一筹莫展，那么建议你提前了解大厂算法面试真题的特点，搭配专属 OJ 平台，有针对性的练习，点击阅读原文一键直达。

OJ 平台：https://oj.algomooc.com/