小白水平理解面试经典题目LeetCode 594 最大和谐字符串-Toy模板网

这篇具有很好参考价值的文章主要介绍了小白水平理解面试经典题目LeetCode 594 最大和谐字符串。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

594 最大和谐字符串

这道题属于字符串类型题目，解决的办法还是有很多的，暴力算法，二分法，双指针等等。

题目描述

和谐数组是指一个数组里元素的最大值和最小值之间的差别正好是 1 。

现在，给你一个整数数组 nums ，请你在所有可能的子序列中找到最长的和谐子序列的长度。

数组的子序列是一个由数组派生出来的序列，它可以通过删除一些元素或不删除元素、且不改变其余元素的顺序而得到。

小白水平理解面试经典题目LeetCode 594 最大和谐字符串,leetcode,面试,leetcode,java

这题一上来描述贼多，例子给的是比较简单的。直接扔出两个例子让你理解，好了，是看着好像是简单的字符串一类。遥想当年还是在大学，坐在教室后排在上听着年老的大学教授讲着C++与字符串是多么的犯困😪，倚着头看着心仪班花的时候。。。啪！继续看题！
小白水平理解面试经典题目LeetCode 594 最大和谐字符串,leetcode,面试,leetcode,java
既然是面试，那咱们可不能让面试官久等了。

小明：OK，完事儿，等着面试官来表扬自己吧。他肯定会说：小子，你是个好手！工位都给你准备好了，工资你说了算。

暴力解法

    public static int longestHarmoniousSubsequence(int[] nums) {
        // 最长和谐子序列的长度
        int maxLength = 0;

        // 遍历所有可能的子序列
        for (int i = 0; i < nums.length; i++) {
            // 当前子序列的长度
            int currentLength = 1;

            // 从当前元素开始向后遍历
            for (int j = i + 1; j < nums.length; j++) {
                // 如果差为 1，则更新当前子序列的长度
                if (Math.abs(nums[i] - nums[j]) == 1) {
                    currentLength += 1;
                } else {
                    // 如果差不为 1，则结束当前子序列
                    break;
                }
            }

            // 如果当前子序列的长度大于最长子序列的长度，则更新最长子序列的长度
            if (currentLength > maxLength) {
                maxLength = currentLength;
            }
        }
        return maxLength;
    }

小白水平理解面试经典题目LeetCode 594 最大和谐字符串,leetcode,面试,leetcode,java

面试官：嗯，你这个要是nums 数组要是给了十万个数是不是会影响性能？

小明OS：今年这个找工市场，人言洛阳花似锦，偏我来时不逢春。。。怎的，技能要求突然涨了，不是做出来就行？

好吧，逼我拿出压箱底的东西是吧。的确这个算法是偏慢一些，但是这不是想着去请班花吃饭么。

这里我个人小白理解分析：

对于最长和谐子序列问题，我们可以使用滑动窗口来维护一个包含所有元素的和谐子序列。窗口的大小为 2，窗口中的元素之差为 1。

具体来说，我们可以从第一个元素开始，遍历整个数组。对于每个元素，我们将其添加到窗口中。如果窗口中的元素之差不为 1，则我们将窗口中的最小元素移出窗口。

这样，我们就可以确保窗口中始终包含一个和谐子序列。

Sliding Window

 public static int findLHS(int[] nums) {
        // 将数组升序排列
        Arrays.sort(nums);
        // 窗口的左边界
        int left = 0;
        // 窗口的右边界
        int right = 1;
        // 最长和谐子序列的长度
        int maxLength = 0; 
        // 每次循环后的数组大小
        int len = 0;
        
        while(right < nums.length) {
            // 计算前后两个指针数字只差
            int diff =  nums[right] - nums[left];
            
            // 如果窗口中的元素之差大于1，并且左指针小于右指针，增加左指针
            while(diff > 1  && left < right) {
                left++;
                diff = nums[right] - nums[left];
            }
            
            // 就算当前符合要求的len长度
            if(nums[right] != nums[left]) {
                len = right - left + 1;
            }
            // 更新最长和谐子序列的长度
            maxLength = Math.max(len, maxLength);
            right++;
        }
        return maxLength;