前缀和+哈希表方法笔记

前言

374周赛Q4没做出来，看了灵神的前缀和+哈希表的文章，学习到一些东西记录一下。

LeetCode： 字母与数字

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
面试题 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.学习到从字符串数组转换到数值数组的思路

2.学习到用位运算区分是数值还是字母

3.可以学习到前缀和+哈希表的使用方法

题解

首先前缀和数组我们是知道的，就不过多说明了，有一个数组arr = [1,-1,2,3,4]，长度是n = 5， 前缀和数组是 d = [0, 0, 2, 5, 9]，长度为n + 1 = 6。前缀和数组两个元素di，dj（i < j）作差就能得到(i, j]之间的元素和。这一题先把复杂的字符串转换为int的数组，因为题目里面只要区分是字母和数字，将字母对应的元素变为1，数字变为-1，就可以抛开字符串的各种不同的值，转为只有1和-1的两个常量的int数组，复杂程度就降低了。

下面是位运算区分数字和字母的位运算操作：

对于任意小写/大写英文字母字符，其 ASCII 码的二进制都形如 01xxxxxx；

对于任意数字字符，其 ASCII 码的二进制都形如 0011xxxx。

根据这一特点，可以根据二进制从低到高第 666 位（设二进制最低位是第 000 位）是 000 还是 111 来判断：如果是 111 就是小写/大写英文字母字符，如果是 000 就是数字字符。把字符的二进制右移 666 位再 AND 1就可以得到这个比特值，1就是字母，0就是数值。接下来在对 0或者1 * 2 - 1，这样就可以得到1或者-1，对应是字母或数字。

接着因为题目要找到的是字母和数值相等，所以是要找到i到j前缀和是d[j] - d[i] = 0，-1+1 = 0，转换为两个前缀和是相同的d[i] = d[j]。题目是找到最长的子数组，所以，就是i-j的距离是最大的，用hashMap记录一个每个前缀和对应的起始下标是多少，如果有多个距离一样的就找起始元素下标是最小的。

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
public class FindLongestSubarrayLcci {

    
    public String[] findLongestSubarray(String[] array) {
        int n = array.length;
        int[] d = new int[n + 1];
        for (int i = 0; i < n; i++) {
            d[i + 1] = d[i] + (array[i].charAt(0) >> 6 & 1) * 2 - 1;
        }

        int max = 0, fIndex = 0;
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i <= n; i++) {
            int t = map.getOrDefault(d[i], -1);
            if (t < 0) {
                // 说明是第一次出现
                map.put(d[i], i);
            } else {
                // 有相同的 说明找到字母和数字相等的子数组了，对比一下下标，找到最大的那个
                if (i - t > max) {
                    max = i - t;
                    fIndex = t;
                }
            }
        }

        if (max == 0) {
            return new String[0];
        }

        String[] ans = new String[max];
        System.arraycopy(array, fIndex, ans, 0, max);
        return ans;
    }
}