面试题 17.05. 字母与数字

题目链接：面试题 17.05. 字母与数字

方法：TwoSum

解题思路

（1）将字符量化为 \(+1\)，数字量化为 \(-1\)，那么当子数组的和\(subSum = 0\)时，表示子数组中的字符和数字的数量相等；
（2）\(subSum = s[j] - s[i]，j >= i，i = 1, 2, ...\)，\(s[i]\)表示前\(i\)个元素的和；
（3）即找\(s[j] - s[i] = 0\)，也即\(s[j] = s[i]\)，且 \((j - i)\) \(is\) \(max\)。

代码

class Solution {
public:
    vector<string> findLongestSubarray(vector<string>& array) {
        int n = array.size();
        int s = 0, mx_len = 0, l = 0;
        unordered_map<int, int> idx{{s, 0}};
        for (int i = 1; i <= n; i ++ ) {
            s += (array[i - 1][0] >> 6 & 1) * 2 - 1; // 字符 +1，数字 -1

            if (idx.count(s)) {
                int curlen = i - idx[s];
                if (curlen > mx_len) {
                    mx_len = curlen;
                    l = idx[s];
                }
            } else {
                idx[s] = i;
            }
        }
        
        return {array.begin() + l, array.begin() + l + mx_len};
    }
};
/*
关于array[i - 1][0] >> 6 & 1操作：
对于字母的ASCII码为 01xx xxxx，而数字的ASCII码为 0011 xxxx；
1、当字母执行上述操作后，结果为 1
2、当数字执行上述操作后，结果为 0
*/

复杂度分析

时间复杂度：\(O(n)\)；
空间复杂度：\(O(n)\)。

相关题目

1. 两数之和
1590. 使数组和能被 P 整除—题解：1590. 使数组和能被 P 整除（TwoSum ！！！）