题目浅析

  • 想查看原题可以点击题目链接。

  • 简单地说，可以对数组做 k 次以内的删除操作，求删除完后数组内最长子数组的长度，该子数组连续。

思路分享

  • 陆爻齐输力，得很很地研究灵茶山艾府的题解才行。

    https://leetcode.cn/problems/find-the-longest-equal-subarray/solutions/2396401/fen-zu-shuang-zhi-zhen-pythonjavacgo-by-lqqau/

  • 这是挺高级的分组滑动窗口，数组内有多少个数字，就有多少个窗口需要滑动，每个窗口的责任是找到自己负责的数组最长连续的情况长度是多少。而这个怎么找的思路就很有意思。

  • 对于每个数值，都有一个唯一对应的数组来保存各个数值在原数组的下标，该对应由哈希表实现。想计算两个相同数值之间有多少个数值（闭区间）只要用两个下标相减加一即可，暂且把这个数值记作 A。

  • 那么如何满足题目中删除最多 k 个数字来保证子数组连续的要求呢？只要找到这两个数在哈希表自己数组中的下标之差，就对应了该区间内，想连续数值的数量，这个数量记作 B。现在，有了一个区间内数字的数量 A，和需要的相同数字的数量 B，只要 A-B 小于 k，那么这个子数组就是满足条件的。把所有的 B 中最大值求出，就是结果。

  • 不过上面的这一条是思路，具体实现时，发现只要记录数值下标时，同时对这个值减去当前哈希表对应数组的长度，就能使得对这个数组的窗口左右相减时的值就是上面的 A-B。毕竟相当于每个数存的是 a1-b1, a2-b2……，任意两个相减就是 a2-a1-(b2-b1), A==a2-a1, B==b2-b1。

代码解答（强烈建议自行解答后再看）

  • 参考题解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int longestEqualSubarray(vector<int>& nums, int k) {
        vector<vector<int>> rec(nums.size()+1);
        for (int i = 0; i < nums.size(); i++) {
            rec[nums[i]].push_back(i-rec[nums[i]].size());
        }
        
        int ans = 0;
        for (const auto &p : rec) {
            int left = 0;
            for (int i = 0; i < p.size(); i++) {
                while(p[i]-p[left]>k) {
                    left++;
                }
                ans = max(ans, i-left+1);
            }
        }
        return ans;
    }
};