Leetcode 3171. Find Subarray With Bitwise AND Closest to K

本文主要是介绍Leetcode 3171. Find Subarray With Bitwise AND Closest to K，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

• Leetcode 3171. Find Subarray With Bitwise AND Closest to K
  • 1. 解题思路
  • 2. 代码实现

• 题目链接：3171. Find Subarray With Bitwise AND Closest to K

1. 解题思路

这道题坦率地说让我感觉很挫败，又一次没有自力搞定，是看了大佬们的答案才搞定的……

知道比没有搞定更难受的是什么吗？是连续两三周好像都没有自力搞定第四题。如果还有的话，那就是有2000号人都把这题搞定了，我依然没搞定……

知道还有什么能比这个更糟心的吗？是我想了一个“优雅”的思路，想要优化执行效率，结果发现还是超时，然后优化了半天之后，只多通过了一个测试样例……真的是心态爆炸……

但是这还不是最坑爹的，最坑爹的是，看了大佬们的解答之后发现，他们居然是暴力解答的，是我一开始就排除掉了的最简单但是最暴力的解法，结果还一次过了……

啊啊啊啊啊！！！！！

Anyway，牢骚发了半天，还是说回到这道题本身吧，我就不说我的算法了，直接说题目的正解吧，就是一个滑动窗口，用一个集合来保存以当前元素为最后一个元素时前方所有的sub array的与结果，然后遍历一轮即可。

原则上来说，这个最坏会是一个$O(N^2)$的算法复杂度的解法，不知道为啥这个居然可以通过，真的是服了……

2. 代码实现

给出python代码实现如下：

class Solution:def minimumDifference(self, nums: List[int], k: int) -> int:prev = set()ans = math.inffor x in nums:prev = set([x] + [x & p for p in prev])ans = min(ans, min(abs(x-k) for x in prev))return ans

提交代码评测得到：耗时1360ms，占用内粗31.6MB。

这篇关于Leetcode 3171. Find Subarray With Bitwise AND Closest to K的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---