comments	difficulty	edit_url
true	困难	https://github.com/doocs/leetcode/edit/main/solution/3100-3199/3171.Find%20Subarray%20With%20Bitwise%20AND%20Closest%20to%20K/README.md

3171. 找到按位与最接近 K 的子数组

English Version

题目描述

给你一个数组 nums 和一个整数 k 。你需要找到 nums 的一个子数组，满足子数组中所有元素按位与运算 AND 的值与 k 的 绝对差 尽可能小。换言之，你需要选择一个子数组 nums[l..r] 满足 |k - (nums[l] AND nums[l + 1] ... AND nums[r])| 最小。

请你返回最小的绝对差值。

子数组是数组中连续的非空元素序列。

示例 1：

输入：nums = [1,2,4,5], k = 3

输出：1

解释：

子数组 nums[2..3] 的按位 AND 运算值为 4 ，得到最小差值 |3 - 4| = 1 。

示例 2：

输入：nums = [1,2,1,2], k = 2

输出：0

解释：

子数组 nums[1..1] 的按位 AND 运算值为 2 ，得到最小差值 |2 - 2| = 0 。

示例 3：

输入：nums = [1], k = 10

输出：9

解释：

只有一个子数组，按位 AND 运算值为 1 ，得到最小差值 |10 - 1| = 9 。

提示：

1 <= nums.length <= 10⁵
1 <= nums[i] <= 10⁹
1 <= k <= 10⁹

解法

方法一：双指针 + 位运算

根据题目描述，我们需要求出数组 $nums$ 下标 $l$ 到 $r$ 的元素的按位与运算的结果，即 $nums[l] & nums[l + 1] & \cdots & nums[r]$。

如果我们每次固定右端点 $r$，那么左端点 $l$ 的范围是 $[0, r]$。每次移动右端点 $r$，按位与的结果只会变小，我们用一个变量 $s$ 记录当前的按位与的结果，如果 $s$ 小于 $k$，我们就将左端点 $l$ 向右移动，直到 $s$ 大于等于 $k$。在移动左端点 $l$ 的过程中，我们需要维护一个数组 $cnt$，记录当前区间内每个二进制位上 $0$ 的个数，当 $cnt[h]$ 为 $0$ 时，说明当前区间内的元素在第 $h$ 位上都为 $1$，我们就可以将 $s$ 的第 $h$ 位设置为 $1$。

时间复杂度 $O(n \times \log M)$，空间复杂度 $O(\log M)$。其中 $n$ 和 $M$ 分别是数组 $nums$ 的长度和数组 $nums$ 中的最大值。

相似题目：

3097. 或值至少为 K 的最短子数组 II

Python3

class Solution:
    def minimumDifference(self, nums: List[int], k: int) -> int:
        m = max(nums).bit_length()
        cnt = [0] * m
        s, i = -1, 0
        ans = inf
        for j, x in enumerate(nums):
            s &= x
            ans = min(ans, abs(s - k))
            for h in range(m):
                if x >> h & 1 ^ 1:
                    cnt[h] += 1
            while i < j and s < k:
                y = nums[i]
                for h in range(m):
                    if y >> h & 1 ^ 1:
                        cnt[h] -= 1
                        if cnt[h] == 0:
                            s |= 1 << h
                i += 1
                ans = min(ans, abs(s - k))
        return ans

Java

class Solution {
    public int minimumDifference(int[] nums, int k) {
        int mx = 0;
        for (int x : nums) {
            mx = Math.max(mx, x);
        }
        int m = 32 - Integer.numberOfLeadingZeros(mx);
        int[] cnt = new int[m];
        int n = nums.length;
        int ans = Integer.MAX_VALUE;
        for (int i = 0, j = 0, s = -1; j < n; ++j) {
            s &= nums[j];
            ans = Math.min(ans, Math.abs(s - k));
            for (int h = 0; h < m; ++h) {
                if ((nums[j] >> h & 1) == 0) {
                    ++cnt[h];
                }
            }
            while (i < j && s < k) {
                for (int h = 0; h < m; ++h) {
                    if ((nums[i] >> h & 1) == 0 && --cnt[h] == 0) {
                        s |= 1 << h;
                    }
                }
                ++i;
                ans = Math.min(ans, Math.abs(s - k));
            }
        }
        return ans;
    }
}

C++

class Solution {
public:
    int minimumDifference(vector<int>& nums, int k) {
        int mx = *max_element(nums.begin(), nums.end());
        int m = 32 - __builtin_clz(mx);
        int n = nums.size();
        int ans = INT_MAX;
        vector<int> cnt(m);
        for (int i = 0, j = 0, s = -1; j < n; ++j) {
            s &= nums[j];
            ans = min(ans, abs(s - k));
            for (int h = 0; h < m; ++h) {
                if (nums[j] >> h & 1 ^ 1) {
                    ++cnt[h];
                }
            }
            while (i < j && s < k) {
                for (int h = 0; h < m; ++h) {
                    if (nums[i] >> h & 1 ^ 1 && --cnt[h] == 0) {
                        s |= 1 << h;
                    }
                }
                ans = min(ans, abs(s - k));
                ++i;
            }
        }
        return ans;
    }
};

Go

func minimumDifference(nums []int, k int) int {
	m := bits.Len(uint(slices.Max(nums)))
	cnt := make([]int, m)
	ans := math.MaxInt32
	s, i := -1, 0
	for j, x := range nums {
		s &= x
		ans = min(ans, abs(s-k))
		for h := 0; h < m; h++ {
			if x>>h&1 == 0 {
				cnt[h]++
			}
		}
		for i < j && s < k {
			y := nums[i]
			for h := 0; h < m; h++ {
				if y>>h&1 == 0 {
					cnt[h]--
					if cnt[h] == 0 {
						s |= 1 << h
					}
				}
			}
			ans = min(ans, abs(s-k))
			i++
		}
	}
	return ans
}

func abs(x int) int {
	if x < 0 {
		return -x
	}
	return x
}

TypeScript

function minimumDifference(nums: number[], k: number): number {
    const m = Math.max(...nums).toString(2).length;
    const n = nums.length;
    const cnt: number[] = numsay(m).fill(0);
    let ans = Infinity;
    for (let i = 0, j = 0, s = -1; j < n; ++j) {
        s &= nums[j];
        ans = Math.min(ans, Math.abs(s - k));
        for (let h = 0; h < m; ++h) {
            if (((nums[j] >> h) & 1) ^ 1) {
                ++cnt[h];
            }
        }
        while (i < j && s < k) {
            for (let h = 0; h < m; ++h) {
                if (((nums[i] >> h) & 1) ^ 1 && --cnt[h] === 0) {
                    s |= 1 << h;
                }
            }
            ans = Math.min(ans, Math.abs(s - k));
            ++i;
        }
    }
    return ans;
}

方法二：哈希表 + 枚举

根据题目描述，我们需要求出数组 $nums$ 下标 $l$ 到 $r$ 的元素的按位与运算的结果，即 $nums[l] & nums[l + 1] & \cdots & nums[r]$。

如果我们每次固定右端点 $r$，那么左端点 $l$ 的范围是 $[0, r]$。由于按位与之和随着 $l$ 的减小而单调递减，并且 $nums[i]$ 的值不超过 $10^9$，因此区间 $[0, r]$ 最多只有 $30$ 种不同的值。因此，我们可以用一个集合来维护所有的 $nums[l] & nums[l + 1] & \cdots & nums[r]$ 的值。当我们从 $r$ 遍历到 $r+1$ 时，以 $r+1$ 为右端点的值，就是集合中每个值与 $nums[r + 1]$ 进行按位与运算得到的值，再加上 $nums[r + 1]$ 本身。因此，我们只需要枚举集合中的每个值，与 $nums[r]$ 进行按位与运算，就可以得到以 $r$ 为右端点的所有值，将每个值与 $k$ 相减后取绝对值，就可以得到以 $r$ 为右端点的所有值与 $k$ 的差的绝对值，其中的最小值就是答案。

时间复杂度 $O(n \times \log M)$，空间复杂度 $O(\log M)$。其中 $n$ 和 $M$ 分别是数组 $nums$ 的长度和数组 $nums$ 中的最大值。

相似题目：

1521. 找到最接近目标值的函数值

Python3

class Solution:
    def minimumDifference(self, nums: List[int], k: int) -> int:
        ans = abs(nums[0] - k)
        s = {nums[0]}
        for x in nums:
            s = {x & y for y in s} | {x}
            ans = min(ans, min(abs(y - k) for y in s))
        return ans

Java

class Solution {
    public int minimumDifference(int[] nums, int k) {
        int ans = Math.abs(nums[0] - k);
        Set<Integer> pre = new HashSet<>();
        pre.add(nums[0]);
        for (int x : nums) {
            Set<Integer> cur = new HashSet<>();
            for (int y : pre) {
                cur.add(x & y);
            }
            cur.add(x);
            for (int y : cur) {
                ans = Math.min(ans, Math.abs(y - k));
            }
            pre = cur;
        }
        return ans;
    }
}

C++

class Solution {
public:
    int minimumDifference(vector<int>& nums, int k) {
        int ans = abs(nums[0] - k);
        unordered_set<int> pre;
        pre.insert(nums[0]);
        for (int x : nums) {
            unordered_set<int> cur;
            cur.insert(x);
            for (int y : pre) {
                cur.insert(x & y);
            }
            for (int y : cur) {
                ans = min(ans, abs(y - k));
            }
            pre = move(cur);
        }
        return ans;
    }
};

Go

func minimumDifference(nums []int, k int) int {
	ans := abs(nums[0] - k)
	pre := map[int]bool{nums[0]: true}
	for _, x := range nums {
		cur := map[int]bool{x: true}
		for y := range pre {
			cur[x&y] = true
		}
		for y := range cur {
			ans = min(ans, abs(y-k))
		}
		pre = cur
	}
	return ans
}

func abs(x int) int {
	if x < 0 {
		return -x
	}
	return x
}

TypeScript

function minimumDifference(nums: number[], k: number): number {
    let ans = Math.abs(nums[0] - k);
    let pre = new Set<number>();
    pre.add(nums[0]);
    for (const x of nums) {
        const cur = new Set<number>();
        cur.add(x);
        for (const y of pre) {
            cur.add(x & y);
        }
        for (const y of cur) {
            ans = Math.min(ans, Math.abs(y - k));
        }
        pre = cur;
    }
    return ans;
}

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

README.md

README.md

3171. 找到按位与最接近 K 的子数组

题目描述

解法

方法一：双指针 + 位运算

Python3

Java

C++

Go

TypeScript

方法二：哈希表 + 枚举

Python3

Java

C++

Go

TypeScript

Files

README.md

Latest commit

History

README.md

File metadata and controls

3171. 找到按位与最接近 K 的子数组

题目描述

解法

方法一：双指针 + 位运算

Python3

Java

C++

Go

TypeScript

方法二：哈希表 + 枚举

Python3

Java

C++

Go

TypeScript