2401-最长优雅子数组

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:31 2023-09-13 16:06:31 Updated    

给你一个由 正 整数组成的数组 nums 。

如果 nums 的子数组中位于 不同 位置的每对元素按位 与（AND） 运算的结果等于 0 ，则称该子数组为 优雅 子数组。

返回 最长 的优雅子数组的长度。

子数组 是数组中的一个 连续 部分。

注意： 长度为 1 的子数组始终视作优雅子数组。

示例 1：

**输入：** nums = [1,3,8,48,10]
**输出：** 3
**解释：** 最长的优雅子数组是 [3,8,48] 。子数组满足题目条件：
- 3 AND 8 = 0
- 3 AND 48 = 0
- 8 AND 48 = 0
可以证明不存在更长的优雅子数组，所以返回 3 。

示例 2：

**输入：** nums = [3,1,5,11,13]
**输出：** 1
**解释：** 最长的优雅子数组长度为 1 ，任何长度为 1 的子数组都满足题目条件。

提示：

  • 1 <= nums.length <= 105
  • 1 <= nums[i] <= 109

请看 视频讲解 第三题。

方法一：暴力枚举

子数组中任意两个数按位与均为 0，意味着任意两个数对应的集合的交集为空（见 从集合论到位运算，常见位运算技巧分类总结 ）。

这意味着子数组中的从低到高的第 i 个比特位上，至多有一个比特 1，其余均为比特 0。例如子数组不可能有两个奇数（最低位为 1)，否则这两个数按位与是大于 0 的。

根据鸽巢原理（抽屉原理），在本题数据范围下，优雅子数组的长度不会超过 30。例如子数组为 [2^0,2^1,2^2,\cdots,2^{29}]，我们无法再加入一个数 x，使 x 与子数组中的任何一个数按位与均为 0。

既然长度不会超过 30，直接暴力枚举子数组的右端点 i 即可。

代码实现时，可以把在子数组中的元素按位或起来（求并集），这样可以 \mathcal{O}(1) 判断当前元素是否与前面的元素按位与的结果为 0（交集为空）。

[sol1-Python3]
1
2
3
4
5
6
7
8
9
10
class Solution:
    def longestNiceSubarray(self, nums: List[int]) -> int:
        ans = 0
        for i, or_ in enumerate(nums):  # 枚举子数组右端点 i
            j = i - 1
            while j >= 0 and (or_ & nums[j]) == 0:  # nums[j] 与子数组中的任意元素 AND 均为 0
                or_ |= nums[j]  # 加到子数组中
                j -= 1  # 向左扩展
            ans = max(ans, i - j)
        return ans
[sol1-Java]
1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public int longestNiceSubarray(int[] nums) {
        int ans = 0;
        for (int i = 0; i < nums.length; i++) { // 枚举子数组右端点 i
            int or = 0, j = i;
            while (j >= 0 && (or & nums[j]) == 0) // nums[j] 与子数组中的任意元素 AND 均为 0
                or |= nums[j--]; // 加到子数组中
            ans = Math.max(ans, i - j);
        }
        return ans;
    }
}
[sol1-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int longestNiceSubarray(vector<int> &nums) {
        int ans = 0;
        for (int i = 0; i < nums.size(); i++) { // 枚举子数组右端点 i
            int or_ = 0, j = i;
            while (j >= 0 && (or_ & nums[j]) == 0) // nums[j] 与子数组中的任意元素 AND 均为 0
                or_ |= nums[j--]; // 加到子数组中
            ans = max(ans, i - j);
        }
        return ans;
    }
};
[sol1-Go]
1
2
3
4
5
6
7
8
9
10
11
12
func longestNiceSubarray(nums []int) (ans int) {
	for i, or := range nums { // 枚举子数组右端点 i
		j := i - 1
		for ; j >= 0 && or&nums[j] == 0; j-- { // nums[j] 与子数组中的任意元素 AND 均为 0
			or |= nums[j] // 加到子数组中
		}
		ans = max(ans, i-j)
	}
	return
}

func max(a, b int) int { if b > a { return b }; return a }

复杂度分析

  • 时间复杂度：\mathcal{O}(n\log U)，其中 n 为 nums 的长度，U=\max(\textit{nums})。
  • 空间复杂度：\mathcal{O}(1)，仅用到若干变量。

方法二：滑动窗口

不了解滑动窗口的同学请看 基础算法精讲 。

进一步地，既然这些数对应的集合的交集为空，我们可以用滑动窗口优化上述过程，右边加入 nums}[\textit{right}]，左边移出 nums}[\textit{left}]。如果 or 与新加入的 nums}[\textit{right}] 有交集，则不断从 or 中去掉集合 nums}[\textit{left}]，直到 or 与 nums}[\textit{right}] 交集为空。

如何把集合语言翻译成位运算代码，见 从集合论到位运算，常见位运算技巧分类总结 。

[sol2-Python3]
1
2
3
4
5
6
7
8
9
10
class Solution:
    def longestNiceSubarray(self, nums: List[int]) -> int:
        ans = left = or_ = 0
        for right, x in enumerate(nums):
            while or_ & x:  # 有交集
                or_ ^= nums[left]  # 从 or_ 中去掉集合 nums[left]
                left += 1
            or_ |= x  # 把集合 x 并入 or_ 中
            ans = max(ans, right - left + 1)
        return ans
[sol2-Java]
1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public int longestNiceSubarray(int[] nums) {
        int ans = 0;
        for (int left = 0, right = 0, or = 0; right < nums.length; right++) {
            while ((or & nums[right]) > 0) // 有交集
                or ^= nums[left++]; // 从 or 中去掉集合 nums[left]
            or |= nums[right]; // 把集合 nums[right] 并入 or 中
            ans = Math.max(ans, right - left + 1);
        }
        return ans;
    }
}
[sol2-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int longestNiceSubarray(vector<int> &nums) {
        int ans = 0;
        for (int left = 0, right = 0, or_ = 0; right < nums.size(); right++) {
            while (or_ & nums[right]) // 有交集
                or_ ^= nums[left++]; // 从 or 中去掉集合 nums[left]
            or_ |= nums[right]; // 把集合 nums[right] 并入 or 中
            ans = max(ans, right - left + 1);
        }
        return ans;
    }
};
[sol2-Go]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
func longestNiceSubarray(nums []int) (ans int) {
	left, or := 0, 0
	for right, x := range nums {
		for or&x > 0 { // 有交集
			or ^= nums[left] // 从 or 中去掉集合 nums[left]
			left += 1
		}
		or |= x // 把集合 x 并入 or 中
		ans = max(ans, right-left+1)
	}
	return
}

func max(a, b int) int { if b > a { return b }; return a }

复杂度分析

  • 时间复杂度：\mathcal{O}(n)，其中 n 为 nums 的长度。
  • 空间复杂度：\mathcal{O}(1)，仅用到若干变量。
 Comments
On this page
2401-最长优雅子数组
  1. 方法一：暴力枚举
  2. 方法二：滑动窗口