LogTrick

LogTrick算法是一种通过利用对数运算性质来优化常见数字运算（如AND、OR、GCD、LCM等）的方法。它通过简化运算复杂度，提升运算效率，尤其适用于处理包含多个元素的数字数组。

LogTrick算法讲解

求解问题

求解数组中位运算子数组的相关问题，一般求解AND,OR,GCD,LCM等问题。

O(nlogU)，U=max(nums),(nums中最大的数)

一些特性

AND的数越多，结果越小；OR的数越多，结果越大。

推导

以AND为例，nums数组取[2,3,6,4]：

for (int i = 0; i < nums.size() ; i ++){
    for (int j = i - 1 ; j >= 0 ; j ++){
        // 得到nums[j:i+1]的子数组
        nums[j] &= nums[i];
    }
}

// 模拟过程如下
//   2             3       6     4  
//  010           011     110   100  (initial)
//  a0                               (i = 0) 
//  a0&a1         a1                 (i = 1)
//  a0&a1&a2     a1&a2     a2        (i = 2)
//  a0&a1&a2&a3 a1&a2&a3 a2&a3  a3   (i = 3)

// 模拟过程如下
//   2   3   6    4  
//  010 011 110  100  (initial)
//  010               (i = 0) 
//  010 011           (i = 1)
//  010 010 110       (i = 2)
//  000 000 100  100  (i = 3)
// 如果再加一个数,       5(101)
//  000 000 100  100   101  (i = 4) 

将每个数的二进制当作集合来处理，AND操作相当于求交集，次数越多范围越小；

回归到集合论中，两个集合求交集，越向左（交集次数越多），范围越小，那么只会存在两种情况：

• nums[j] & nums[i] != nums[j]，两集合相交，但并不是子集，需要进一步遍历。
• nums[j] & nums[i] == nums[j]，不变根据集合论，说明nums[j]是nums[i]的子集，完全覆盖，也就是说再往左计算，范围更小，更小的子集，故不再进行下一步计算。

回归到代码中，可能会有疑问了，这不是两个for吗，那时间复杂度不就是n^2吗？其实并不是，参考leetcode3097题的数据范围，nums[i]的上界是10^9，所以它是小于2^30的，也就是说数字最大只有29位；而我们知道AND操作每次结果不相同，最多也就是29次，故内层循环最多执行29次，即整个算法时间复杂度为O(nlogU)，在这道题中logU为29。

leetcode

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

class Solution {
public:
    int minimumSubarrayLength(vector<int>& nums, int k) {
        int ans = INT_MAX;
        for (int i = 0 ; i < nums.size() ; i ++){
            if (nums[i] >= k){return 1;}
            for (int j = i - 1 ; j >= 0 ; j --){
                if ((nums[j] | nums[i]) == nums[j]){break;}
                nums[j] |= nums[i];
                if (nums[j] >= k){
                    ans = min(ans , i - j + 1);
                }
            }
        }
        return ans == INT_MAX ? -1 : ans;
    }
};

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

class Solution {
public:
    int minimumDifference(vector<int>& nums, int k) {
        int ans = INT_MAX;
        for (int i = 0 ; i < nums.size() ; i ++){
            int x = nums[i];
            ans = min(ans , abs(x - k));
            for (int j = i - 1 ; j >= 0 ; j--){
                if ((nums[j] | x) == nums[j]){break;}
                nums[j] |= x;
                ans = min(ans , abs(nums[j] - k));
            }
        }
        return ans;
    }
};

2411. 按位或最大的最小子数组长度

class Solution {
public:
    vector<int> smallestSubarrays(vector<int>& nums) {
        vector<int> ans(nums.size());
        for (int i = 0 ; i < nums.size() ; i++){
            ans[i] = 1;
            for (int j = i - 1 ; j >= 0 ; j--){
                if ((nums[j] | nums[i]) == nums[j]){break;}
                // 如果变一定是变大
                nums[j] |= nums[i];
                ans[j] = i - j + 1;
            }
        }
        return ans;
    }
};

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

class Solution {
public:
    int closestToTarget(vector<int>& nums, int k) {
        int ans = INT_MAX;
        for (int i = 0 ; i < nums.size() ; i ++){
            int x = nums[i];
            ans = min(ans , abs(x - k));
            for (int j = i - 1 ; j >= 0 ; j--){
                if ((nums[j] & x) == nums[j]){break;}
                nums[j] &= x;
                ans = min(ans , abs(nums[j] - k));
            }
        }
        return ans;
    }
};

898. 子数组按位或操作

class Solution {
public:
    int subarrayBitwiseORs(vector<int>& nums) {
        map<int , bool> myMap;
        for (int i = 0 ; i < nums.size() ; i ++){
            int x = nums[i];
            myMap.insert({x , true});
            for (int j = i - 1 ; j >= 0 ; j--){
                if ((nums[j] | x) == nums[j]){break;}
                nums[j] |= x;
                if (myMap.find(nums[j]) == myMap.end()){
                    myMap.insert({nums[j] , true});
                }
            }
        }
        return myMap.size();
    }
};