[leetcode 3171][备忘录][Go]关于LogTrick解法的个人理解

题目连接

leetcode 3171

参考链接

灵茶山艾府 - leetcode 3171题解

解题思路

主要目的就是算出所有子数组的按位运算值并算出与k的绝对差，暴力解法时间复杂度为$O(n^2)$且题目中nums.length最大值为$10^5$肯定会超时

为了更好理解，设一对指针l/r和一个数组dp[]，dp[l]表示nums[r]|nums[r-1]|nums[r-2]...nums[l]的值，即子数组r至l的按位与运算值(当r后移时dp[0]至dp[r]中的值会被覆盖)

LogTrick的思路就是利用当a|b=b时a|b|c|d|e == b|c|d|e的特点省去大量的重复计算(最终时间复杂度能达到$O(n \log U)(U=max(nums))$)，即当(nums[r]|dp[l]) == dp[l]就可以直接跳过dp[l-1]到dp[0]的计算，因为此时dp[l],dp[l-1],dp[l-2]…dp[0]与上一个r边界的值完全相同

1
2
3
4
5
6
7
8
9
var dp = make([]int, len(nums))
var ret = abs(nums[0]-k)
for r := range nums {
    //当(nums[r]|dp[l])==dp[l]时就跳出循环后移r
    for l := r; l >= 0 && (nums[r]|dp[l]) != dp[l]; l-- {
        dp[l] |= nums[r]
        ret = min(ret, asb(dp[l]-k))
    }
}

为什么时间复杂度为$O(n \log U)$

假设0 <= nums[i] < 16，即nums[i]为一个4位二进制数，那么对于nums = []int{8, 4, 2, 1, 1, 2, 4, 8}的二进制形式如下:

1
2
3
4
5
6
7
8
1000
0100
0010
0001
0001
0010
0100
1000

当r在0,1,2,3时因为每一位都只有一个一所以都需要计算到底，分别计算了1,2,3,4次但从r为4,5,6,7时会在l为0,1,2,3时就出现(nums[r]|dp[l])==dp[l]的情况所以计算次数都为5次

也就按位或运算呈递增单调性导致平均每位的累积变化都不会超过n次这也使得计算次数不会超过$n \log U$