golang 解法, 执行用时: 84 ms, 内存消耗: 8.6 MB, 提交时间: 2023-09-18 17:43:50

// 与运算性质，两个都是1才是1，与运算只会不变变小或者不变，与运算
// 满足结合律和交换律 ands数组从左往右数值不断减小
// 相等的数的右端点就会组成一个区间,需要去重，采用原地去重方法

func closestToTarget(arr []int, target int) int {
	n := len(arr)
	ans := math.MaxInt32
	type pair struct{ or, i int }
	ands := []pair{} // 按位与的值 + 对应子数组的右端点的最小值
	for i := n - 1; i >= 0; i-- {
		num := arr[i]
		ands = append(ands, pair{num, i})
		ands[0].or &= num
		ans = min(ans, abs(ands[0].or-target))
		k := 0
		for _, p := range ands[1:] {
			p.or &= num
			if ands[k].or == p.or {
				ands[k].i = p.i // 合并相同值，下标取最小的
			} else {
				ans = min(ans, abs(p.or-target))
				k++ // 下标++
				ands[k] = p
			}
		}
		ands = ands[:k+1] // 去掉多余的部分
	}
	return ans
}

func min(a, b int) int { if a < b { return a }; return b }
func abs(x int) int { if x < 0 { return -x }; return x }

java 解法, 执行用时: 108 ms, 内存消耗: 54.6 MB, 提交时间: 2023-09-18 17:41:53

class Solution {
    public int closestToTarget(int[] arr, int target) {
        HashSet<Integer> cur = new HashSet<>();
        int min = Integer.MAX_VALUE;
        for(int i : arr){
            HashSet<Integer> cur2 = new HashSet<>();
            cur2.add(i);
            min = Math.min(min,Math.abs(target-i));
            for(int j : cur){
                int val = j&i;
                cur2.add(val);
                min = Math.min(min,Math.abs(target-val));
            }
            cur = cur2;
        }
        return min;
    }
}

cpp 解法, 执行用时: 576 ms, 内存消耗: 151 MB, 提交时间: 2023-09-18 17:40:55

class Solution {
public:
    int closestToTarget(vector<int>& arr, int target) {
        int ans = abs(arr[0] - target);
        vector<int> valid = {arr[0]};
        for (int num: arr) {
            vector<int> validNew = {num};
            ans = min(ans, abs(num - target));
            for (int prev: valid) {
                validNew.push_back(prev & num);
                ans = min(ans, abs((prev & num) - target));
            }
            validNew.erase(unique(validNew.begin(), validNew.end()), validNew.end());
            valid = validNew;
        }
        return ans;
    }
};

python3 解法, 执行用时: 728 ms, 内存消耗: 26.2 MB, 提交时间: 2023-09-18 17:40:18

# 按位与性质
class Solution:
    def closestToTarget(self, arr: List[int], target: int) -> int:
        ans = abs(arr[0] - target)
        valid = {arr[0]}
        for num in arr:
            valid = {x & num for x in valid} | {num}
            ans = min(ans, min(abs(x - target) for x in valid))
        return ans