LeetCode 面试题 17.05. 字母与数字

Categories:

题目描述
思路分析
1. 解法一：前缀差值 + 哈希表（推荐）
相似题目

题目描述

✅ 面试题 17.05. 字母与数字

思路分析

解法一：前缀差值 + 哈希表（推荐）

核心思路：

把字母记为 +1，数字记为 -1，前缀和相等表示区间内字母数字数量相等。

记录每个前缀差值第一次出现的位置。

对每个位置计算最长区间并更新答案。

复杂度分析：

时间复杂度：O(n)，其中 n 表示数组长度。

空间复杂度：O(n)。

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

class Solution {
    public String[] findLongestSubarray(String[] array) {
        Map<Integer, Integer> first = new HashMap<>();
        first.put(0, -1);
        int diff = 0;
        int bestStart = 0;
        int bestLen = 0;

        for (int i = 0; i < array.length; i++) {
            char ch = array[i].charAt(0);
            if (Character.isDigit(ch)) {
                diff--;
            } else {
                diff++;
            }

            if (!first.containsKey(diff)) {
                first.put(diff, i);
            }

            int start = first.get(diff);
            int len = i - start;
            if (len > bestLen) {
                bestLen = len;
                bestStart = start + 1;
            }
        }

        String[] res = new String[bestLen];
        System.arraycopy(array, bestStart, res, 0, bestLen);
        return res;
    }
}

func findLongestSubarray(array []string) []string {
	first := make(map[int]int)
	first[0] = -1
	diff := 0
	bestStart := 0
	bestLen := 0

	for i := 0; i < len(array); i++ {
		ch := array[i][0]
		if ch >= '0' && ch <= '9' {
			diff--
		} else {
			diff++
		}

		if _, ok := first[diff]; !ok {
			first[diff] = i
		}

		start := first[diff]
		length := i - start
		if length > bestLen {
			bestLen = length
			bestStart = start + 1
		}
	}

	return array[bestStart : bestStart+bestLen]
}

相似题目

题目	难度	考察点
525. 连续数组	中等	前缀和
560. 和为K的子数组	中等	前缀和
1248. 统计「优美子数组」	中等	前缀和
523. 连续的子数组和	中等	前缀和
930. 和相同的二元子数组	中等	前缀和

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2022/60114818