LeetCode |
您所在的位置：网站首页 › 1-150数字表格 › LeetCode |
LeetCode
|
我们可以使用能够前缀和来表示当前数组中字母和数字出现次数之差，若出现字母则将前缀和加一，若出现数字则将前缀和减一。而后我们在哈希表中查找当前前缀和是否存在：1、若存在，我们判断当前位置的前缀和与第一次出现前缀和的距离是否大于当前的最大子数组长度，若大于则对子数组长度与起始位置进行更新；2、若不存在，我们向哈希表中储存当前前缀和与出现位置之间的映射关系。最终我们只需要按照记录返回最长子数组即可。 class Solution { public: vector findLongestSubarray(vector& array) { unordered_map indices; indices[0] = -1; int sum = 0; int maxLength = 0; int startIndex = -1; int n = array.size(); for (int i = 0; i sum++; } else { sum--; } if (indices.count(sum)) { int firstIndex = indices[sum]; if (i - firstIndex > maxLength) { maxLength = i - firstIndex; startIndex = firstIndex + 1; } } else { indices[sum] = i; } } if (maxLength == 0) { return {}; } return vector(array.begin() + startIndex, array.begin() + startIndex + maxLength); } }; |
【本文地址】
今日新闻 |
推荐新闻 |