面试题17.05.字母与数字

链接：面试题17.05.字母与数字
难度：Medium
标签：数组、哈希表、前缀和
简介：给定一个放有字母和数字的数组，找到最长的子数组，且包含的字母和数字的个数相同。返回该子数组，若存在多个最长子数组，返回左端点下标值最小的子数组。若不存在这样的数组，返回一个空数组。

题解 1 - cpp

• 编辑时间：2023-03-11
• 执行用时：160ms
• 内存消耗：92.1MB
• 编程语言：cpp
• 解法介绍：前缀和。

class Solution {
public:
    vector<string> findLongestSubarray(vector<string>& array) {
        int cur = 0, resMax = 0, resIdx = -1;
        unordered_map<int, int> m;
        m[0] = -1;
        for (int i = 0; i < array.size(); i++) {
            cur += isalpha(array[i][0]) ? 1 : -1;
            if (m.count(cur) && i - m[cur] > resMax) resIdx = m[cur] + 1, resMax = i - m[cur];
            if (!m.count(cur)) m[cur] = i;
        }
        vector<string> res;
        for (int i = resIdx; i < resIdx + resMax; i++) res.push_back(array[i]);
        return res;
    }
};

题解 2 - python

• 编辑时间：2023-03-11
• 执行用时：108ms
• 内存消耗：32.6MB
• 编程语言：python
• 解法介绍：同上。

class Solution:
    def findLongestSubarray(self, array: List[str]) -> List[str]:
        cur, resMax, resIdx = 0, 0, -1
        m = dict()
        m[0] = -1
        for i in range(len(array)):
            cur += 1 if array[i].isalpha() else -1
            if cur in m and i - m[cur] > resMax:
                resIdx = m[cur] + 1
                resMax = i - m[cur]
            if cur not in m:
                m[cur] = i
        return array[resIdx:resIdx + resMax]

题解 3 - rust

• 编辑时间：2023-03-11
• 执行用时：84ms
• 内存消耗：11.4MB
• 编程语言：rust
• 解法介绍：同上。

impl Solution {
    pub fn find_longest_subarray(array: Vec<String>) -> Vec<String> {
        let (mut cur, mut resMax, mut resIdx) = (0, 0, 0);
        let mut m = std::collections::HashMap::<i32, i32>::new();
        m.insert(0, -1);
        for i in 0..array.len() {
            let s = array[i].chars().collect::<Vec<char>>();
            cur += if s[0].is_alphabetic() { 1 } else { -1 };
            if m.contains_key(&cur) && i as i32 - *m.get(&cur).unwrap() > resMax {
                resIdx = *m.get(&cur).unwrap() + 1;
                resMax = i as i32 - *m.get(&cur).unwrap();
            }
            if !m.contains_key(&cur) {
                m.insert(cur, i as i32);
            }
        }
        let resMax = resMax as usize;
        let resIdx = resIdx as usize;
        array[resIdx..resIdx + resMax].to_vec()
    }
}