力扣---面试题 17.05. 字母与数字

标签：力扣 面试题 前缀 int 字母 --- 数组 array 数字

面试题 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

通过次数23,015   提交次数49,755

---

前缀和，总感觉是对昨天那道题的巩固（虽然昨天那题搞不懂的是那几个公式。。。）

class Solution {
    public String[] findLongestSubarray(String[] array) {
        // 存储前缀和
        int sum = 0;
        // 存储第一个下标
        int res0 = 0;
        // 存储第二个下标
        int res1 = 0;
        // 哈希表，存储出现过的前缀和和其第一次出现时的位置。
        Map<Integer, Integer> map = new HashMap<>();
        // 在刚开始的地方，前缀和一定等于0
        map.put(0, 0);
        for (int i = 0; i < array.length; ++ i) {
            char a = array[i].charAt(0);
            // 数字
            if (a <= '9') {
                sum ++;
                // 字母
            } else {
                sum --;
            }
            // 如果已经出现了相同的前缀和，意味着两者中间的所有前缀和相加等于0，即意味着符合题目要求的数字和字母出现次数相同。
            if (map.containsKey(sum)) {
                // 如果间隔更大，更新答案即可。
                if (res1 - res0 < i - map.get(sum)) {
                    res0 = map.get(sum);
                    res1 = i;
                }
            // i + 1是因为计算的前缀和是包含第i项的，需要保存的是第i+1的位置
            } else {
                map.put(sum, i + 1);
            }
        }
        // 意味着没有进行更新，即不包含符合题意的子数组
        if (res0 == res1) {
            return new String[0];
        }
        String[] ans = new String[res1 + 1 - res0];
        // 复制，由于左闭右开，所以需要进行+1.
        System.arraycopy(array, res0, ans, 0, res1 + 1 - res0);
        return ans;
    }
}

 

 

标签：力扣,面试题,前缀,int,字母,---,数组,array,数字
From： https://www.cnblogs.com/allWu/p/17207058.html