class Solution {
public:
int longestNiceSubarray(vector<int>& nums) {
}
};
2401. 最长优雅子数组
给你一个由 正 整数组成的数组 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 <= 1051 <= nums[i] <= 109原站题解
golang 解法, 执行用时: 80 ms, 内存消耗: 10 MB, 提交时间: 2023-06-17 09:15:57
func longestNiceSubarray(nums []int) (ans int) {
left, or := 0, 0
for right, x := range nums {
for or&x > 0 {
or ^= nums[left]
left += 1
}
or |= x
ans = max(ans, right-left+1)
}
return
}
func max(a, b int) int { if b > a { return b }; return a }
golang 解法, 执行用时: 84 ms, 内存消耗: 9.9 MB, 提交时间: 2023-06-17 09:15:48
func longestNiceSubarray(nums []int) (ans int) {
for i, or := range nums {
j := i - 1
for ; j >= 0 && or&nums[j] == 0; j-- {
or |= nums[j]
}
ans = max(ans, i-j)
}
return
}
func max(a, b int) int { if b > a { return b }; return a }
cpp 解法, 执行用时: 96 ms, 内存消耗: 55.8 MB, 提交时间: 2023-06-17 09:15:31
class Solution {
public:
int longestNiceSubarray(vector<int> &nums) {
int ans = 0;
for (int i = 0; i < nums.size(); ++i) {
int or_ = 0, j = i;
while (j >= 0 && (or_ & nums[j]) == 0)
or_ |= nums[j--];
ans = max(ans, i - j);
}
return ans;
}
};
cpp 解法, 执行用时: 100 ms, 内存消耗: 55.7 MB, 提交时间: 2023-06-17 09:15:23
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[right];
ans = max(ans, right - left + 1);
}
return ans;
}
};
java 解法, 执行用时: 3 ms, 内存消耗: 54.1 MB, 提交时间: 2023-06-17 09:14:40
class Solution {
public int longestNiceSubarray(int[] nums) {
int ans = 0;
for (int i = 0; i < nums.length; ++i) {
int or = 0, j = i;
while (j >= 0 && (or & nums[j]) == 0)
or |= nums[j--];
ans = Math.max(ans, i - j);
}
return ans;
}
}
java 解法, 执行用时: 2 ms, 内存消耗: 54 MB, 提交时间: 2023-06-17 09:14:30
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[right];
ans = Math.max(ans, right - left + 1);
}
return ans;
}
}
python3 解法, 执行用时: 580 ms, 内存消耗: 30.7 MB, 提交时间: 2023-06-17 09:14:18
# 双指针
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]
left += 1
or_ |= x
ans = max(ans, right - left + 1)
return ans
python3 解法, 执行用时: 556 ms, 内存消耗: 30.6 MB, 提交时间: 2023-06-17 09:14:01
# 暴力枚举
class Solution:
def longestNiceSubarray(self, nums: List[int]) -> int:
ans = 0
for i, or_ in enumerate(nums):
j = i - 1
while j >= 0 and (or_ & nums[j]) == 0:
or_ |= nums[j]
j -= 1
ans = max(ans, i - j)
return ans