跳转至

面试题 17.05. 字母与数字

题目描述

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

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

示例 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$，那么问题就转化为：求最长的子数组，使得该子数组的和为 $0$。

我们可以运用前缀和的思想，用哈希表 $vis$ 记录每个前缀和第一次出现的位置，用变量 $mx$ 和 $k$ 分别记录最长的满足条件的子数组的长度和左端点位置。

接下来遍历数组，计算当前位置 $i$ 的前缀和 $s$：

  • 如果当前位置的前缀和 $s$ 在哈希表 $vis$ 中存在，我们记第一次出现 $s$ 的位置为 $j$，那么区间 $[j + 1,..,i]$ 的子数组和就为 $0$。如果此前的最长子数组的长度小于当前子数组的长度，即 $mx \lt i - j$，我们就更新 $mx = i - j$ 和 $k = j + 1$。
  • 否则，我们将当前位置的前缀和 $s$ 作为键，当前位置 $i$ 作为值，存入哈希表 $vis$ 中。

遍历结束后，返回左端点为 $k$，且长度为 $mx$ 的子数组即可。

时间复杂度 $O(n)$，空间复杂度 $O(n)$。其中 $n$ 为数组的长度。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution:
    def findLongestSubarray(self, array: List[str]) -> List[str]:
        vis = {0: -1}
        s = mx = k = 0
        for i, x in enumerate(array):
            s += 1 if x.isalpha() else -1
            if s in vis:
                if mx < i - (j := vis[s]):
                    mx = i - j
                    k = j + 1
            else:
                vis[s] = i
        return array[k : k + mx]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public String[] findLongestSubarray(String[] array) {
        Map<Integer, Integer> vis = new HashMap<>();
        vis.put(0, -1);
        int s = 0, mx = 0, k = 0;
        for (int i = 0; i < array.length; ++i) {
            s += array[i].charAt(0) >= 'A' ? 1 : -1;
            if (vis.containsKey(s)) {
                int j = vis.get(s);
                if (mx < i - j) {
                    mx = i - j;
                    k = j + 1;
                }
            } else {
                vis.put(s, i);
            }
        }
        String[] ans = new String[mx];
        System.arraycopy(array, k, ans, 0, mx);
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    vector<string> findLongestSubarray(vector<string>& array) {
        unordered_map<int, int> vis{{0, -1}};
        int s = 0, mx = 0, k = 0;
        for (int i = 0; i < array.size(); ++i) {
            s += array[i][0] >= 'A' ? 1 : -1;
            if (vis.count(s)) {
                int j = vis[s];
                if (mx < i - j) {
                    mx = i - j;
                    k = j + 1;
                }
            } else {
                vis[s] = i;
            }
        }
        return vector<string>(array.begin() + k, array.begin() + k + mx);
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
func findLongestSubarray(array []string) []string {
    vis := map[int]int{0: -1}
    var s, mx, k int
    for i, x := range array {
        if x[0] >= 'A' {
            s++
        } else {
            s--
        }
        if j, ok := vis[s]; ok {
            if mx < i-j {
                mx = i - j
                k = j + 1
            }
        } else {
            vis[s] = i
        }
    }
    return array[k : k+mx]
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
function findLongestSubarray(array: string[]): string[] {
    const vis = new Map();
    vis.set(0, -1);
    let s = 0,
        mx = 0,
        k = 0;
    for (let i = 0; i < array.length; ++i) {
        s += array[i] >= 'A' ? 1 : -1;
        if (vis.has(s)) {
            const j = vis.get(s);
            if (mx < i - j) {
                mx = i - j;
                k = j + 1;
            }
        } else {
            vis.set(s, i);
        }
    }
    return array.slice(k, k + mx);
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    func findLongestSubarray(_ array: [String]) -> [String] {
        var vis: [Int: Int] = [0: -1]
        var s = 0, mx = 0, k = 0

        for i in 0..<array.count {
            s += array[i].first!.isLetter ? 1 : -1
            if let j = vis[s] {
                if mx < i - j {
                    mx = i - j
                    k = j + 1
                }
            } else {
                vis[s] = i
            }
        }

        return Array(array[k..<(k + mx)])
    }
}

评论