面试题 17.05. 字母与数字

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * 思路：
 * 数字看成-1，字母看成1，再计算前缀和。
 * 哈希表记录第一次出现前缀和的下标。
 * 前缀和相同则计算下标的差值。
 */
public class Solution {

    public String[] findLongestSubarray(String[] array) {
        // 前缀和
        int s = 0;
        // 保存第一次
        Map<Integer, Integer> m = new HashMap<>();
        // 前缀和数组，保存该前缀和第一次出现时，数组的下标
        int[] sum = new int[array.length];
        // 最长的字母和数字个数相同的子数组的长度
        int max = 0;
        // 子数组起始下标
        int start = 0;
        // 题目中只要求数字和字母个数相同，跟数字和字母具体是多少没关系。所以将数字看成 -1，字母看成 1，类似于线段树中离散化的思想。
        for (int i = 0; i < array.length; i++) {
            char c = array[i].charAt(0);
            if (c >= '0' && c <= '9') {
                // 数字 -1
                s--;
            } else {
                // 字母 + 1
                s++;
            }
            // 前缀和等于0的情况，[0,i] 区间内所有元素的和为 0，即数字和字母个数相同。区间长度为 i+1
            if (s == 0 && i + 1 > max) {
                start = 0;
                max = i + 1;
            }
            // 填充前缀和数组
            sum[i] = s;
            // 该前缀和第一次出现时的下标
            Integer prefixFist = m.get(s);
            if (prefixFist != null) {
                // 当前下标 i 减去第一次出现该前缀和的下标 prefixFist，计算出区间长度
                if (i - prefixFist > max) {
                    // 举个例子 前缀和为 1 0 1，下标分别为 0 1 2，第一次出现前缀和为 1 的下标为 0，第二次出现前缀和的下标为 2。区间 0 1 的长度为 2 - 0 = 2
                    start = prefixFist + 1;
                    max = i - prefixFist;
                }
            } else {
                m.put(s, i);
            }
        }
        // 返回最长子数组
        String[] copy = new String[max];
        System.arraycopy(array, start, copy, 0, max);
        return copy;
    }
}

作者：xiu-qiang-jiang
链接：https://leetcode.cn/problems/find-longest-subarray-lcci/solution/by-xiu-qiang-jiang-g8j9/
来源：力扣（LeetCode）