题目分析

这个题目的数据范围是数组长度小于等于1e5，因此我们不能使用$O(n^2)$或者以上时间复杂度的算法进行求解。

哈希表

这个题目和Leetcode第一题非常相似。我们可以设定一个计数器val，当数字出现时，val++，否则val–。一开始val=0。当两次val相同时，说明这中间的字符满足数字和字母相同。

因此我们将计数器第一次出现的位置保存下来，如0号字符是数字，val = 1，那么我们将用map记录一个pair{1, 0}，当第8个字符遍历后，发现val = 1。因此我们查看map中已经有了key=1的键值对，我们就可以知道从1号到8号这8个字符中数字和字母是相同的。因为从1号开始val++和val–次数相同。如果长度大于之前保存的最大长度，则替换，如果长度相等，比较起始的字符串的大小。如果小于之前的则替换即可。

此题要注意要给哈希表赋初值，当一个字符都没有时，索引为-1。即map = { {0, -1} }，否则在特殊情况下会得到错误结果。如[“A”, “1”]，当遍历到第二个元素时，val = 0，发现并没有key = 0的键值对，因此会创建一个{0, 1}的键值对，这就是不正确的。

算法的**时间复杂度为$O(n)$，空间复杂度为$O(n)$**。

#include<iostream>
#include<vector>

using namespace std;

class Solution {
public:
    vector<string> findLongestSubarray(vector<string>& array) {
        int val = 0, begin = 0, length = 0;
        map<int, int> m = { {0, -1} };
        for (int i = 0; i < array.size(); i++) {
            if (array[i][0] >= '0' && array[i][0] <= '9') val++;
            else val--;
            if (!m.count(val)) m[val] = i;
            else if(i - m[val] > length || (i - m[val] == length && array[m[val] + 1] < array[begin + 1])) begin = m[val] + 1, length = i - m[val];
        }
        return vector<string>(array.begin() + begin, array.begin() + begin + length);
    }
};

刷题总结

两数之和是Leetcode的入坑题，其中包含了非常重要的思想，在今后的做题过程中会反复用到，小伙伴们务必理解它。