此题解采用了分治与双指针的策略。首先，它将输入数组分为两部分，分别计算每部分可能的子序列和，存储在两个列表中。对于计算子序列和的过程，使用了一个集合来避免重复和。每次从当前子序列和集合中取一个元素，并与当前数字相加，形成新的子序列和，更新到集合中。然后对两个结果列表排序，并使用双指针技术来找到两个列表中元素之和最接近目标值的组合。指针的移动根据当前和与目标值的比较结果进行：如果和小于目标值，则移动较小列表的指针；如果和大于目标值，则移动较大列表的指针。这种方法可以有效地缩小搜索范围，直到找到最小的绝对差。
时间复杂度: O(2^(n/2) log(2^(n/2)))
空间复杂度: O(2^(n/2))
class Solution:
def sub_squence_sum(self, nums):
sum_result = set([0]) # 存储所有可能的子序列和
new_result = set() # 临时存储新增的子序列和
for n in nums: # 遍历数组中的每个元素
for s in sum_result: # 遍历已存在的子序列和
new_result.add(s + n) # 将当前元素添加到已有子序列和中
sum_result.update(new_result) # 更新子序列和集合
new_result.clear() # 清空临时集合
sum_result = list(sum_result) # 转换为列表以便排序
sum_result.sort() # 排序
return sum_result
def minAbsDifference(self, nums: List[int], goal: int) -> int:
if len(nums) == 0:
return abs(goal)
split_pos = len(nums) // 2 # 将数组分为两部分
res1 = self.sub_squence_sum(nums[:split_pos]) # 计算前半部分的子序列和
res2 = self.sub_squence_sum(nums[split_pos:]) # 计算后半部分的子序列和
i = 0 # res1 的索引
j = len(res2) - 1 # res2 的索引
min_diff = math.inf # 初始化最小差值
while True: # 使用双指针查找最接近的和
if i < len(res1) and j >= 0:
diff = res1[i] + res2[j] - goal # 计算当前子序列和与目标值的差
min_diff = min(abs(diff), min_diff) # 更新最小差值
if diff == 0: # 如果差值为0，直接返回
return 0
elif diff > 0: # 如果差值大于0，移动 j 减小和
j -= 1
elif diff < 0: # 如果差值小于0，移动 i 增大和
i += 1
elif i >= len(res1) and j >= 0:
min_diff = min(abs(res1[-1] + res2[j] - goal), min_diff) # 仅移动 j
j -= 1
elif i < len(res1) and j < 0:
min_diff = min(abs(res1[i] + res2[0] - goal), min_diff) # 仅移动 i
i += 1
else:
break # 所有可能已遍历完毕
return min_diff