原文链接: https://leetcode-cn.com/problems/find-longest-subarray-lcci

英文原文

Given an array filled with letters and numbers, find the longest subarray with an equal number of letters and numbers.

Return the subarray. If there are more than one answer, return the one which has the smallest index of its left endpoint. If there is no answer, return an empty arrary.

Example 1:

Input: ["A","1","B","C","D","2","3","4","E","5","F","G","6","7","H","I","J","K","L","M"]

Output: ["A","1","B","C","D","2","3","4","E","5","F","G","6","7"]

Example 2:

Input: ["A","A"]

Output: []

Note:

• array.length <= 100000

中文题目

给定一个放有字母和数字的数组，找到最长的子数组，且包含的字母和数字的个数相同。

返回该子数组，若存在多个最长子数组，返回左端点下标值最小的子数组。若不存在这样的数组，返回一个空数组。

示例 1:

输入: ["A","1","B","C","D","2","3","4","E","5","F","G","6","7","H","I","J","K","L","M"]

输出: ["A","1","B","C","D","2","3","4","E","5","F","G","6","7"]

示例 2:

输入: ["A","A"]

输出: []

提示：

• array.length <= 100000

通过代码

高赞题解

思路

数字看成-1，字母看成1，再计算前缀和。
前缀和 相同则计算下标的差值。

技巧：使用int[]数组memo存储 该前缀和 第1次出现时 的下标。
为何是第1次出现时的下标？
因为要求最长子数组。

比如：
["A","1","B","C","D","2","3","4","E","5","F","G","6","7","H","I","J","K","L","M"]

转化为[1, -1, 1, 1, 1, -1, -1, -1, 1, -1, 1, 1, -1, -1, 1, 1, 1, 1, 1, 1]

再转为前缀和形式[1, 0, 1, 2, 3, 2, 1, 0, 1, 0, 1, 2, 1, 0, 1, 2, 3, 4, 5, 6]。

前缀和相同是什么意思呢？

比如看加粗的2个1：[1, 0, 1, 2, 3, 2, 1, 0, 1, 0, 1, 2, 1, 0, 1, 2, 3, 4, 5, 6]

说明这2个1的下标所构成的区间内的数字和为0，而数字和为0说明有相同个数的1和-1，即相同个数的字母和数字。

具体来说：第1个加粗的1下标为0，第2个加粗的1下标为2，构成区间(0, 2](注意：是半开半闭)，
区间(0, 2]内元素的和即下标为1和下标为2的元素之和，[1, -1, 1, 1, 1, -1, -1, -1, 1, -1, 1, 1, -1, -1, 1, 1, 1, 1, 1, 1]
很明显-1 + 1 = 0

理解了这一点，剩余的工作就是找前缀和相同，且相隔最远的2个元素。

什么才是相隔最远？

[1, 0, 1, 2, 3, 2, 1, 0, 1, 0, 1, 2, 1, 0, 1, 2, 3, 4, 5, 6]

单只看前缀和为1的情况，毫无疑问，前缀和为1时，相隔最远的肯定是最左边的1和最右边的1.

因此我们只需要记录前缀和为1第一次出现时的下标即可(也就是记录了最左边的1的位置)，以后再遇到前缀和为1时，只需要将其下标 - 所记录的最左边的1的位置 即可。

至于memo数组大小为何初始化为(len << 1) + 1，考虑最极端的情况，要么全为-1，要么全为1，对应前缀和为-array.length和array.length。

特别注意:
当前缀和为0时，假设其下标为n，则说明区间[0, n]内所有元素的和为0，区间长度为n + 1。
因此将memo[0 + array.length]的值设为-1，因为n - (-1) = n + 1。

同时由于数组下标不能为负数，因此需要映射处理:
假设数组有2个元素，边界值为-2和2，即[-2, -1, 0, 1, 2]。
将[-2, -1, 0, 1, 2] 集体右移nums.length个单位，映射为[0, 1, 2, 3, 4]。

代码

[-java代码]
class Solution {
    public String[] findLongestSubarray(String[] array) {
        int len = array.length;
        int[] memo = new int[(len << 1) + 1];
        Arrays.fill(memo, -2);
        memo[len] = -1;
        int res = 0, count = 0, begin = 0, end = 0;
        for (int i = 0; i < len; ++i) {
            boolean is_num = true;
            for (char c : array[i].toCharArray())
                if (c < '0' || c > '9') {
                    is_num = false;
                    break;
                }
            count += is_num ? -1 : 1;
            //未曾见过该前缀和(即memo数组中没有记录)
            if (memo[count + len] <= -2) 
                memo[count + len] = i;  //记录该前缀和的下标
            //曾见过该前缀和(即memo数组中已有记录)
            else if (i - memo[count + len] > res) {
                begin = memo[count + len] + 1;
                end = i + 1;
                res = i - memo[count + len];
            }
        }
        return Arrays.copyOfRange(array, begin, end);
    }
}

[-c++代码]
class Solution {
public:
    vector<string> findLongestSubarray(vector<string>& array) {
        size_t len = array.size();
        vector<int> memo((len << 1) + 1, -2);
        memo[len] = -1;
        size_t begin = 0, end = 0;
        int res = 0, count = 0;
        for (size_t i = 0; i < len; ++i) {
            bool is_num = true;
            for (const auto& ch : array[i])
                if (ch < '0' || ch > '9') {
                    is_num = false;
                    break;
                }
            count += is_num ? -1 : 1;
            if (memo[count + len] <= -2) 
                memo[count + len] = i;
            else if (i - memo[count + len] > res) {
                begin = memo[count + len] + 1;
                end = i + 1;
                res = i - memo[count + len];
            }
        }
        return vector<string>(array.begin() + begin, array.begin() + end);
    }
};

[-python3代码]
class Solution:
    def findLongestSubarray(self, array: List[str]) -> List[str]:
        array_len = len(array)
        memo = [-2 for i in range((array_len << 1) + 1)]
        memo[array_len] = -1
        begin, end = 0, 0
        res, count = 0, 0
        for i in range(array_len):
            is_num = True
            for ch in array[i]:
                if (ord(ch) < ord('0')) or (ord(ch) > ord('9')):
                    is_num = False
                    break
            count += -1 if is_num else 1
            if memo[count + array_len] <= -2:
                memo[count + array_len] = i
            elif i - memo[count + array_len] > res:
                begin, end = memo[count + array_len] + 1, i + 1
                res = i - memo[count + array_len]
        return array[begin:end]

统计信息

通过次数	提交次数	AC比率
5857	15057	38.9%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言