Interview questions 17.05. Letters and numbers

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

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/find-longest-subarray-lcci

解法1

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/** * 思路： * digital as-1,See the letters as1,再计算前缀和. * The hash table records the subscript of the first occurrence of the prefix sum. * If the prefix sum is the same, the difference of the subscripts is calculated. */
public class Solution {
    

    public String[] findLongestSubarray(String[] array) {
    
        // 前缀和
        int s = 0;
        // Save the first time
        Map<Integer, Integer> m = new HashMap<>();
        // 前缀和数组,Save the prefix and the first occurrence,数组的下标
        int[] sum = new int[array.length];
        // The length of the longest subarray with the same number of letters and numbers
        int max = 0;
        // Subarray start index
        int start = 0;
        // Only the same number of numbers and letters are required in the question,It doesn't matter how many numbers and letters are there.So think of the numbers as -1,See the letters as 1,Similar to the idea of ​​discretization in line segment trees.
        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] The sum of all elements in the interval is  0,That is, the number of numbers and letters are the same.区间长度为 i+1
            if (s == 0 && i + 1 > max) {
    
                start = 0;
                max = i + 1;
            }
            // Fill prefix and array
            sum[i] = s;
            // The prefix and the first occurrence of the subscript
            Integer prefixFist = m.get(s);
            if (prefixFist != null) {
    
                // 当前下标 i Subtract the subscript of the first occurrence of the prefix sum prefixFist,Calculate the interval length
                if (i - prefixFist > max) {
    
                    // 举个例子 前缀和为 1 0 1,下标分别为 0 1 2,The first occurrence of the prefix sum is  1 的下标为 0,The subscript of the second occurrence of the prefix sum is  2.区间 0 1 的长度为 2 - 0 = 2
                    start = prefixFist + 1;
                    max = i - prefixFist;
                }
            } else {
    
                m.put(s, i);
            }
        }
        // Returns the longest subarray
        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）