[Leetcode][594. 最长和谐子序列] 4种方法：暴力枚举，排序 + 枚举，哈希表

发表于 更新于 分类于 阅读次数： 本文字数： 4.5k 阅读时长 ≈ 4 分钟

By Long Luo

Leetcode 594. 最长和谐子序列 题目如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
594. 最长和谐子序列

和谐数组是指一个数组里元素的最大值和最小值之间的差别正好是1。
现在，给你一个整数数组nums，请你在所有可能的子序列中找到最长的和谐子序列的长度。

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

示例 1：
输入：nums = [1,3,2,2,5,2,3,7]
输出：5
解释：最长的和谐子序列是 [3,2,2,2,3]

示例 2：
输入：nums = [1,2,3,4]
输出：2

示例 3：
输入：nums = [1,1,1,1]
输出：0

提示：
1 <= nums.length <= 2 * 10^4
-10^9 <= nums[i] <= 10^9

方法一：暴力枚举

考虑nums\textit{nums}中的两个数xx，yy，其下标分别为ii，jj，那么满足数组的和谐子序列只有下列2种情况：

  1. x≤y≤x+1x \leq y \leq x + 1，且∣y−x∣=1|y - x| = 1；
  2. x−1≤y≤xx - 1 \leq y \leq x，且∣y−x∣=1|y - x| = 1。

首先想到的方法是22个循环，分别统计上述情况的最大值并更新，即为答案。

代码如下所示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
// BF time: O(n^2) space: O(1)
public int findLHS(int[] nums) {
	int len = nums.length;
	int ans = 0;
	for (int i = 0; i < len; i++) {
		int minDiff = 0;
		int maxDiff = 0;
		int cntMin = 0;
		int cntMax = 0;
		for (int j = 0; j < len; j++) {
			if (nums[j] >= nums[i] && nums[j] <= nums[i] + 1) {
				minDiff += nums[j] - nums[i];
				cntMin++;
			}

			if (nums[j] >= nums[i] - 1 && nums[j] <= nums[i]) {
				maxDiff += nums[j] - nums[i];
				cntMax++;
			}
		}

		cntMin = minDiff >= 1 ? cntMin : 0;
		cntMax = maxDiff >= 1 ? cntMax : 0;
		ans = Math.max(ans, Math.max(cntMin, cntMax));
	}

	return ans;
}

复杂度分析：

  • 时间复杂度：O(N2)O(N^2)，其中NN是数组nums\textit{nums}的长度。
  • 空间复杂度：O(1)O(1)，需要常数个空间保存中间变量。

方法二：排序 + 双指针

思路与算法：

方法一中因为需要对2种情况都进行处理，所以代码非常繁琐且耗时，如果先进行排序，从最小值开始计算。

虽然题干说不能修改数字顺序，所以最开始我并没有想到排序，但实际上我们分析可以看出和排序无关，因为最大最小之差为11，所以实际结果是和数字顺序无关的。

所以我们可以将数组按照从小到大进行排序，然后依次找到相邻两个连续相同元素的子序列，检查该这两个子序列的元素的之差是否为11。

利用滑动窗口的做法，left\textit{left}指向第一个连续相同元素的子序列的第一个元素，right\textit{right}指向相邻的第二个连续相同元素的子序列的末尾元素，如果满足二者的元素之差为11，则当前的和谐子序列的长度即为两个子序列的长度之和，等于right−left+1\textit{right} - \textit{left} + 1。

代码如下所示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public int findLHS(int[] nums) {
    Arrays.sort(nums);
    int len = nums.length;
    int left = 0;
    int ans = 0;
    for (int right = 0; right < len; right++) {
        while (nums[right] - nums[left] > 1) {
            left++;
        }

        if (nums[right] - nums[left] == 1) {
            ans = Math.max(ans, right - left + 1);
        }
    }

    return ans;
}

复杂度分析：

  • 时间复杂度：O(Nlog⁡N)O(N\log N)，其中NN是数组nums\textit{nums}的长度。因为需要对数组进行排序，花费的时间复杂度为O(Nlog⁡N)O(N\log N)，然后利用双指针遍历数组花费的时间为O(2N)O(2N)，总的时间复杂度T(N)=O(Nlog⁡N)+O(2N)=O(Nlog⁡N)T(N) = O(N\log N) + O(2N) = O(N\log N)。

  • 空间复杂度：O(1)O(1)，需要常数个空间保存中间变量。

方法三：HashMap

思路与算法：

因为题目要求是统计最大子序列长度，很容易想到使用HashMap来统计元素出现次数，首先遍历一次，统计各个元素的多少。

第二次遍历，则再使用第2个HashMap，用于存储之前已出现的数值，然后计算出最长的一个子数列，代码如下所示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public int findLHS(int[] nums) {
    int len = nums.length;
    int ans = 0;
    Map<Integer, Integer> freq = new HashMap<>();
    for (int x : nums) {
        freq.put(x, freq.getOrDefault(x, 0) + 1);
    }

    Map<Integer, Integer> has = new HashMap<>();
    for (int i = 0; i < len; i++) {
        has.put(nums[i], has.getOrDefault(nums[i], 0) + 1);
        if (freq.getOrDefault(nums[i] + 1, 0) == 0 && freq.getOrDefault(nums[i] - 1, 0) == 0) {
            continue;
        }
        int plus = freq.get(nums[i]) - has.get(nums[i]) + 1 + freq.getOrDefault(nums[i] + 1, 0) - has.getOrDefault(nums[i] + 1, 0);
        int minus = freq.get(nums[i]) - has.get(nums[i]) + 1 + freq.getOrDefault(nums[i] - 1, 0) - has.getOrDefault(nums[i] - 1, 0);
        ans = Math.max(ans, Math.max(plus, minus));
    }

    return ans;
}

复杂度分析：

  • 时间复杂度：O(N)O(N)，其中NN是数组nums\textit{nums}的长度。

  • 空间复杂度：O(N)O(N)，其中NN是数组nums\textit{nums}的长度，使用了2个HashMap，因此空间复杂度度为O(N)O(N)。

方法四：优化HashMap

思路与算法：

分析方法三，我们发现实际上可以存在很多优化空间，第二个HashMap是没有必要的，因为明显是重复计算了，于是我们有了下面的优化代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public int findLHS(int[] nums) {
    int ans = 0;
    Map<Integer, Integer> freq = new HashMap<>();
    for (int x : nums) {
        freq.put(x, freq.getOrDefault(x, 0) + 1);
    }

    for (int x : nums) {
        if (freq.getOrDefault(x + 1, 0) == 0 && freq.getOrDefault(x - 1, 0) == 0) {
            continue;
        }
        int plus = freq.get(x) + freq.getOrDefault(x + 1, 0);
        int minus = freq.get(x) + freq.getOrDefault(x - 1, 0);
        ans = Math.max(ans, Math.max(plus, minus));
    }

    return ans;
}

上述代码还存在优化的空间，因为注意到会出现重复的数值，所以我们可以只迭代Map中的key值即可，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public int findLHS(int[] nums) {
    int ans = 0;
    Map<Integer, Integer> freq = new HashMap<>();
    for (int x : nums) {
        freq.put(x, freq.getOrDefault(x, 0) + 1);
    }

    for (int key : freq.keySet()) {
        if (freq.containsKey(key + 1)) {
            int temp = freq.get(key) + freq.get(key + 1);
            ans = Math.max(ans, temp);
        }
    }

    return ans;
}

复杂度分析：

  • 时间复杂度：O(N)O(N)，其中NN是数组nums\textit{nums}的长度。

  • 空间复杂度：O(N)O(N)，其中NN是数组nums\textit{nums}的长度，使用了1个HashMap，因此空间复杂度度为O(N)O(N)。

All suggestions are welcome.
If you have any query or suggestion please comment below.
Please upvote👍 if you like💗 it. Thank you:-)

Explore More Leetcode Solutions. 😉😃💗