尧图网页设计 
LeetCode 1521 题解找到最接近目标值的函数值——子数组按位与的单调性与滚动集合枚举法【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcodeLeetCode 1521找到最接近目标值的函数值是 LeetCode 中一道综合考察位运算单调性与枚举状态压缩的典型题目给定数组arr与目标值target需要在 O(N²) 个子数组arr[l:r]中找出使按位与结果func(arr, l, r) arr[l] arr[l1] ... arr[r]与target之差的绝对值最小的取值。本文基于本仓库题解problems/1521.find-a-value-of-a-mysterious-function-closest-to-target.md展开从按位与的单调性出发给出以索引 i 结尾的子数组的完备枚举框架并借助哈希集合压缩状态把朴素 O(N²) 暴力优化到 O(N·C)其中 C 与位宽相关、不超过 32最终在 N ≤ 10^5 的约束下顺利通过。读完本文你将掌握位运算结果数量有界这一高频套路并能直接套用到 898. 子数组按位或操作、201. 数字范围按位与 等同类题目上。一、题目概述与数据范围Winston 构造了一个函数func对整数数组arr的任意合法下标l, r满足0 l, r arr.length其返回值为arr[l..r]全体元素的按位与func(arr, l, r) arr[l] arr[l1] ... arr[r]题目要求返回|func(arr, l, r) - target|的最小值即所有子数组按位与结果中与target距离最近的那个距离。示例 1arr [9,12,3,7,15], target 5所有可能的[l,r]数对共 15 个对应函数值为[9,12,3,7,15,8,0,3,7,0,0,3,0,0,0]最接近 5 的值是 7 和 3最小差值为2。示例 2arr [1000000,1000000,1000000], target 1由于a a a幂等性所有函数值均为1000000最小差值为999999。示例 3arr [1,2,4,8,16], target 0取l r时函数值为对应元素本身其中arr[0] 1与target 0的差值为1但注意[0,2]子数组1 2 4 0直接命中target因此最小差值为0。约束条件1 arr.length 10^51 arr[i] 10^60 target 10^7若采用朴素的 O(N²) 枚举N 10^5 时约 5×10^9 个子数组必然超时因此必须利用按位与的数学性质来压缩枚举规模。二、前置知识本题的题解将 前置知识 定位为两类位运算需要熟悉按位与的运算规则及其单调性质。仓库中的 位运算专题 系统总结了异或、按位与等位运算题目的套路如 136、137、260、645 等题可作为本专题的配套阅读。动态规划本题利用以索引 i 结尾的子数组递推滚动更新状态思想与动态规划的滚动数组一致可参考仓库 动态规划专题。三、核心思路第一步识别按位与的单调性首先要抓住一个关键前提对一个固定右端点 r子数组arr[l:r]的按位与结果关于左端点 l 满足单调性即arr[l:r] arr[l1:r] arr[l2:r] ...也就是说子数组越长l 越小、包含元素越多按位与的结果越小子数组越短结果越大。其数学依据是按位与运算在每一位上的逻辑为1 x x、0 x 0因此一个数 A 与另一个数 B 做按位与其结果不会大于 A也不会大于 B即A B A且A B B。每一次把新的元素与进来只能让某些二进制位从 1 翻转为 0永远不可能从 0 翻转为 1一旦某一位变成 0在更长包含更多元素的子数组中该位将恒为 0。说明原文档中一个数异或另外一个数的结果一定不会比这两个数大一句中的异或应为笔误——异或并不满足该性质如1 ^ 2 3 1真正满足结果不超过参与运算的任一数的是按位与这里已按与运算的语义还原。这一单调性与 201. 数字范围按位与 中连续区间按位与结果只保留前 m 位公共前缀 1、其余位全部为 0的性质同源是本题一切优化手段的根基。第二步借力以索引 i 结尾的子数组完备枚举法为了更好理解枚举框架原题解引入了一个更简单的铺垫问题如果让你求一个数组的连续子数组总个数你会如何求比如[1,3,4]其连续子数组有[1], [3], [4], [1,3], [3,4], [1,3,4]共 6 个。经典做法是总的连续子数组个数 以索引 0 结尾的子数组个数 以索引 1 结尾的子数组个数 … 以索引 n-1 结尾的子数组个数。以每个下标作为右端点划分集合彼此不相交且覆盖全部子数组因此是完备的。这种按右端点分类的计数思路即前缀和思想的延伸仓库中的 一次搞定前缀和 对此有更系统的讲解。本题采用完全相同的枚举策略所有子数组的按位与结果 以索引 0 结尾的子数组按位与结果集合 ∪ 以索引 1 结尾的子数组按位与结果集合 ∪ ... ∪ 以索引 n-1 结尾的子数组按位与结果集合由于要求的是与 target 最接近的值而非总和只需在枚举过程中用全局变量ans记录abs(结果 - target)的最小值即可。第三步递推关系与滚动集合设sub[i]为以索引 i 结尾的所有子数组按位与结果的集合则递推关系非常简洁sub[i] { a b | b ∈ sub[i-1] } ∪ { arr[i] }其中a arr[i]。原因在于以 i 结尾的子数组要么是以 i-1 结尾的某个子数组再拼接上arr[i]对应b a要么是只含单个元素的子数组[arr[i]]对应自身a。这提示我们使用滚动数组只需要维护上一轮的sub[i-1]本轮现场计算出sub[i]并替换无需存储全部 n 个集合空间由 O(N²) 降至 O(C)。这也是原题解中以索引 i 结尾的子数组按位与操作的结果sub[i]其实就等于sub[i-1] A[i]的由来。第四步用哈希集合去重、压缩状态规模朴素地使用普通数组保存sub[i]每个集合的规模随 i 增长会达到 O(N)整体仍是 O(N²)。但按位与结果中大量重复值是毫无意义的因此应使用哈希集合set来去重。去重之后集合规模存在一个与数据范围强相关的上界因为arr[i] 10^6 2^20所有按位与结果都是 20 位以内的二进制数。回顾单调性——以 i 结尾的子数组随左端点从 i 向 0 扩展按位与结果单调不增且每一位一旦从 1 变为 0 就永远不会恢复。因此从全 1 状态逐步丢失1 位最多只能产生位数 1种不同的结果即不超过 21 种。保守估计C集合大小上界不会超过 32。这正是原题解中C 不会超过 32的完整推理。这种解法本质上仍是聪明的暴力枚举与动态规划的关系在于它借用了滚动数组式的状态递推但并没有引入最优子结构与决策因此原文档评价它和动态规划没有啥区别——重点是利用位运算单调性把每轮状态压缩到常数级别。四、关键点识别函数 func 的单调性按位与结果随子数组变长而单调不增每位 1→0 不可逆这是整个算法的理论支柱采用合适的枚举方法按以索引 i 结尾的子数组对全部 O(N²) 个子数组做完备划分避免遗漏同时天然支持递推用哈希集合去重重复的按位与结果无信息量去重后集合规模被位宽限制在常数级时间、空间双降。五、代码实现代码支持语言Python3与仓库题解一致。class Solution: def closestToTarget(self, A: List[int], target: int) - int: seen set() # 滚动集合当前保存的是 sub[i-1] ans float(inf) # 全局最优距离 for a in A: seen.add(a) # 子数组 [i, i] 自身即单元素情况 t set() # 临时集合本轮计算 sub[i]避免迭代中修改 seen # 类似滚动数组此时的 seen 相当于 sub[i-1] for b in seen: yu a b # 以 i 结尾、且长度 2 的子数组与结果 ans min(ans, abs(yu - target)) t.add(yu) # 此时的 t 就是 sub[i]滚动更新回 seen seen t return ans代码流程拆解seen初始化空集ans初始化为正无穷遍历A中的每个元素a即右端点 i先把单元素子数组[i, i]的与结果a加入seen对应递推式中的∪ {arr[i]}部分遍历上一轮的seen即sub[i-1]中的每个值b计算yu a b并同步更新ans收集到临时集合t中用t整体替换seen完成滚动更新进入下一轮。实现细节必须使用临时集合t承接本轮结果而不是直接往seen里加。因为t的内容基于seen的完整快照计算若边遍历边修改seen会导致本轮新增的值被重复参与与运算产生错误的递推结果。这一防坑手法与 898. 子数组按位或操作 题解中pres/nxt双集合的用法完全一致。六、复杂度分析令 N 为数组长度C 为seen集合的大小上界。时间复杂度$O(N \times C)$。外层遍历 N 个元素内层遍历每轮的seen规模不超过 C。由前文分析C 与数据位宽相关、不超过 32因此实际复杂度约为 O(32N)在 N 10^5 时完全可以接受。空间复杂度$O(C)$。仅需维护两个滚动集合不随 N 增长。七、同类题目对比把枚举 去重套路迁移到按位或以索引 i 结尾的子数组 哈希集合滚动去重是位运算子数组类题目的通用框架本仓库中有两题可作为直接对照898. 子数组按位或操作题目要求统计所有子数组按位或结果的不同取值个数。其题解采用完全同构的算法用pres记录以 i-1 结尾的子数组或值集合遍历时对每个pre计算a | pre并连同a自身放入下一轮集合nxt最后用ans | nxt汇总去重。区别仅在于运算符由换成|单调性方向相反按位或结果随子数组变长单调不减每位 0→1 不可逆集合规模同样被位宽限制在常数级。201. 数字范围按位与题目要求[m, n]区间内所有数字的按位与。其性质连续数字求与时前 m 位保持为 1、其余位为 0正是按位与单调性的另一面解题时通过同步右移m、n直到相等来定位公共前缀再左移还原与本题1 位一旦翻转为 0 便永久保持的观察互为印证。三题放在一起可以沉淀出一条清晰的可迁移套路遇到枚举所有连续子数组的位运算结果类问题先论证结果的单调性与数量上界由位宽决定再按右端点分类 集合滚动去重即可把 O(N²) 暴力压缩到近似线性。八、小结LeetCode 1521 的完整解题链路可以浓缩为三步证单调按位与只会把 1 位变 0 位结果随子数组变长单调不增——这是状态可压缩的前提定枚举按以索引 i 结尾的子数组完备分类推出sub[i] {a b | b ∈ sub[i-1]} ∪ {a}的滚动递推压状态用哈希集合去重借助arr[i] 10^6 2^20的位宽限制把每轮状态压缩到不超过 32 个值最终以 O(N·C)、O(C) 的时间和空间完成求解。仓库中该题的完整题解见 problems/1521.find-a-value-of-a-mysterious-function-closest-to-target.md同类的位运算题解可按 位运算专题 与 README 仓库结构 继续检索把单调性 右端点分类 集合去重这套组合拳练熟位运算子数组类题目便可迎刃而解。【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 LeetCode 1521 题解：找到最接近目标值的函数值——子数组按位与的单调性与滚动集合枚举法
LeetCode 1521 题解找到最接近目标值的函数值——子数组按位与的单调性与滚动集合枚举法【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcodeLeetCode 1521找到最接近目标值的函数值是 LeetCode 中一道综合考察位运算单调性与枚举状态压缩的典型题目给定数组arr与目标值target需要在 O(N²) 个子数组arr[l:r]中找出使按位与结果func(arr, l, r) arr[l] arr[l1] ... arr[r]与target之差的绝对值最小的取值。本文基于本仓库题解problems/1521.find-a-value-of-a-mysterious-function-closest-to-target.md展开从按位与的单调性出发给出以索引 i 结尾的子数组的完备枚举框架并借助哈希集合压缩状态把朴素 O(N²) 暴力优化到 O(N·C)其中 C 与位宽相关、不超过 32最终在 N ≤ 10^5 的约束下顺利通过。读完本文你将掌握位运算结果数量有界这一高频套路并能直接套用到 898. 子数组按位或操作、201. 数字范围按位与 等同类题目上。一、题目概述与数据范围Winston 构造了一个函数func对整数数组arr的任意合法下标l, r满足0 l, r arr.length其返回值为arr[l..r]全体元素的按位与func(arr, l, r) arr[l] arr[l1] ... arr[r]题目要求返回|func(arr, l, r) - target|的最小值即所有子数组按位与结果中与target距离最近的那个距离。示例 1arr [9,12,3,7,15], target 5所有可能的[l,r]数对共 15 个对应函数值为[9,12,3,7,15,8,0,3,7,0,0,3,0,0,0]最接近 5 的值是 7 和 3最小差值为2。示例 2arr [1000000,1000000,1000000], target 1由于a a a幂等性所有函数值均为1000000最小差值为999999。示例 3arr [1,2,4,8,16], target 0取l r时函数值为对应元素本身其中arr[0] 1与target 0的差值为1但注意[0,2]子数组1 2 4 0直接命中target因此最小差值为0。约束条件1 arr.length 10^51 arr[i] 10^60 target 10^7若采用朴素的 O(N²) 枚举N 10^5 时约 5×10^9 个子数组必然超时因此必须利用按位与的数学性质来压缩枚举规模。二、前置知识本题的题解将 前置知识 定位为两类位运算需要熟悉按位与的运算规则及其单调性质。仓库中的 位运算专题 系统总结了异或、按位与等位运算题目的套路如 136、137、260、645 等题可作为本专题的配套阅读。动态规划本题利用以索引 i 结尾的子数组递推滚动更新状态思想与动态规划的滚动数组一致可参考仓库 动态规划专题。三、核心思路第一步识别按位与的单调性首先要抓住一个关键前提对一个固定右端点 r子数组arr[l:r]的按位与结果关于左端点 l 满足单调性即arr[l:r] arr[l1:r] arr[l2:r] ...也就是说子数组越长l 越小、包含元素越多按位与的结果越小子数组越短结果越大。其数学依据是按位与运算在每一位上的逻辑为1 x x、0 x 0因此一个数 A 与另一个数 B 做按位与其结果不会大于 A也不会大于 B即A B A且A B B。每一次把新的元素与进来只能让某些二进制位从 1 翻转为 0永远不可能从 0 翻转为 1一旦某一位变成 0在更长包含更多元素的子数组中该位将恒为 0。说明原文档中一个数异或另外一个数的结果一定不会比这两个数大一句中的异或应为笔误——异或并不满足该性质如1 ^ 2 3 1真正满足结果不超过参与运算的任一数的是按位与这里已按与运算的语义还原。这一单调性与 201. 数字范围按位与 中连续区间按位与结果只保留前 m 位公共前缀 1、其余位全部为 0的性质同源是本题一切优化手段的根基。第二步借力以索引 i 结尾的子数组完备枚举法为了更好理解枚举框架原题解引入了一个更简单的铺垫问题如果让你求一个数组的连续子数组总个数你会如何求比如[1,3,4]其连续子数组有[1], [3], [4], [1,3], [3,4], [1,3,4]共 6 个。经典做法是总的连续子数组个数 以索引 0 结尾的子数组个数 以索引 1 结尾的子数组个数 … 以索引 n-1 结尾的子数组个数。以每个下标作为右端点划分集合彼此不相交且覆盖全部子数组因此是完备的。这种按右端点分类的计数思路即前缀和思想的延伸仓库中的 一次搞定前缀和 对此有更系统的讲解。本题采用完全相同的枚举策略所有子数组的按位与结果 以索引 0 结尾的子数组按位与结果集合 ∪ 以索引 1 结尾的子数组按位与结果集合 ∪ ... ∪ 以索引 n-1 结尾的子数组按位与结果集合由于要求的是与 target 最接近的值而非总和只需在枚举过程中用全局变量ans记录abs(结果 - target)的最小值即可。第三步递推关系与滚动集合设sub[i]为以索引 i 结尾的所有子数组按位与结果的集合则递推关系非常简洁sub[i] { a b | b ∈ sub[i-1] } ∪ { arr[i] }其中a arr[i]。原因在于以 i 结尾的子数组要么是以 i-1 结尾的某个子数组再拼接上arr[i]对应b a要么是只含单个元素的子数组[arr[i]]对应自身a。这提示我们使用滚动数组只需要维护上一轮的sub[i-1]本轮现场计算出sub[i]并替换无需存储全部 n 个集合空间由 O(N²) 降至 O(C)。这也是原题解中以索引 i 结尾的子数组按位与操作的结果sub[i]其实就等于sub[i-1] A[i]的由来。第四步用哈希集合去重、压缩状态规模朴素地使用普通数组保存sub[i]每个集合的规模随 i 增长会达到 O(N)整体仍是 O(N²)。但按位与结果中大量重复值是毫无意义的因此应使用哈希集合set来去重。去重之后集合规模存在一个与数据范围强相关的上界因为arr[i] 10^6 2^20所有按位与结果都是 20 位以内的二进制数。回顾单调性——以 i 结尾的子数组随左端点从 i 向 0 扩展按位与结果单调不增且每一位一旦从 1 变为 0 就永远不会恢复。因此从全 1 状态逐步丢失1 位最多只能产生位数 1种不同的结果即不超过 21 种。保守估计C集合大小上界不会超过 32。这正是原题解中C 不会超过 32的完整推理。这种解法本质上仍是聪明的暴力枚举与动态规划的关系在于它借用了滚动数组式的状态递推但并没有引入最优子结构与决策因此原文档评价它和动态规划没有啥区别——重点是利用位运算单调性把每轮状态压缩到常数级别。四、关键点识别函数 func 的单调性按位与结果随子数组变长而单调不增每位 1→0 不可逆这是整个算法的理论支柱采用合适的枚举方法按以索引 i 结尾的子数组对全部 O(N²) 个子数组做完备划分避免遗漏同时天然支持递推用哈希集合去重重复的按位与结果无信息量去重后集合规模被位宽限制在常数级时间、空间双降。五、代码实现代码支持语言Python3与仓库题解一致。class Solution: def closestToTarget(self, A: List[int], target: int) - int: seen set() # 滚动集合当前保存的是 sub[i-1] ans float(inf) # 全局最优距离 for a in A: seen.add(a) # 子数组 [i, i] 自身即单元素情况 t set() # 临时集合本轮计算 sub[i]避免迭代中修改 seen # 类似滚动数组此时的 seen 相当于 sub[i-1] for b in seen: yu a b # 以 i 结尾、且长度 2 的子数组与结果 ans min(ans, abs(yu - target)) t.add(yu) # 此时的 t 就是 sub[i]滚动更新回 seen seen t return ans代码流程拆解seen初始化空集ans初始化为正无穷遍历A中的每个元素a即右端点 i先把单元素子数组[i, i]的与结果a加入seen对应递推式中的∪ {arr[i]}部分遍历上一轮的seen即sub[i-1]中的每个值b计算yu a b并同步更新ans收集到临时集合t中用t整体替换seen完成滚动更新进入下一轮。实现细节必须使用临时集合t承接本轮结果而不是直接往seen里加。因为t的内容基于seen的完整快照计算若边遍历边修改seen会导致本轮新增的值被重复参与与运算产生错误的递推结果。这一防坑手法与 898. 子数组按位或操作 题解中pres/nxt双集合的用法完全一致。六、复杂度分析令 N 为数组长度C 为seen集合的大小上界。时间复杂度$O(N \times C)$。外层遍历 N 个元素内层遍历每轮的seen规模不超过 C。由前文分析C 与数据位宽相关、不超过 32因此实际复杂度约为 O(32N)在 N 10^5 时完全可以接受。空间复杂度$O(C)$。仅需维护两个滚动集合不随 N 增长。七、同类题目对比把枚举 去重套路迁移到按位或以索引 i 结尾的子数组 哈希集合滚动去重是位运算子数组类题目的通用框架本仓库中有两题可作为直接对照898. 子数组按位或操作题目要求统计所有子数组按位或结果的不同取值个数。其题解采用完全同构的算法用pres记录以 i-1 结尾的子数组或值集合遍历时对每个pre计算a | pre并连同a自身放入下一轮集合nxt最后用ans | nxt汇总去重。区别仅在于运算符由换成|单调性方向相反按位或结果随子数组变长单调不减每位 0→1 不可逆集合规模同样被位宽限制在常数级。201. 数字范围按位与题目要求[m, n]区间内所有数字的按位与。其性质连续数字求与时前 m 位保持为 1、其余位为 0正是按位与单调性的另一面解题时通过同步右移m、n直到相等来定位公共前缀再左移还原与本题1 位一旦翻转为 0 便永久保持的观察互为印证。三题放在一起可以沉淀出一条清晰的可迁移套路遇到枚举所有连续子数组的位运算结果类问题先论证结果的单调性与数量上界由位宽决定再按右端点分类 集合滚动去重即可把 O(N²) 暴力压缩到近似线性。八、小结LeetCode 1521 的完整解题链路可以浓缩为三步证单调按位与只会把 1 位变 0 位结果随子数组变长单调不增——这是状态可压缩的前提定枚举按以索引 i 结尾的子数组完备分类推出sub[i] {a b | b ∈ sub[i-1]} ∪ {a}的滚动递推压状态用哈希集合去重借助arr[i] 10^6 2^20的位宽限制把每轮状态压缩到不超过 32 个值最终以 O(N·C)、O(C) 的时间和空间完成求解。仓库中该题的完整题解见 problems/1521.find-a-value-of-a-mysterious-function-closest-to-target.md同类的位运算题解可按 位运算专题 与 README 仓库结构 继续检索把单调性 右端点分类 集合去重这套组合拳练熟位运算子数组类题目便可迎刃而解。【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考