// 外层遍历数组每个元素 for (let i = 0; i < n; i++) { // 内层遍历从0到外层元素之间的每一个元素 for (let j = 0; j < 1 << i; j++) { res[(1 << i) + j] = res[j] + nums[i] } }
return res }
/** * @description * 单调不减的数组nums1和nums2分别找到两个数,其和与target的差最小 返回这个最小差值 */ functiontwoSum(nums1: number[], nums2: number[], target: number) { let l = 0 let r = nums2.length - 1 let res = Infinity
while (l < nums1.length && r > -1) { const sum = nums1[l] + nums2[r] res = Math.min(res, Math.abs(target - sum)) if (sum === target) return0 elseif (sum > target) r-- else l++ }
let res = Infinity for (let leftCount = 0; leftCount <= midIndex; leftCount++) { const left = leftSubArraySum[leftCount].sort((a, b) => a - b) const right = rightSubArraySum[midIndex - leftCount].sort((a, b) => a - b) res = Math.min(res, twoSum(left, right, target)) } return res
/** * @description 计算nums的子序列和 下标表示由多少个数组成 * @summary 时间复杂度O(2^n) */ functiongetSubArraySumFrom(nums: number[]): number[][] { const n = nums.length const res = Array.from<number, number[]>({ length: nums.length + 1 }, () => []) for (let i = 0; i < 1 << n; i++) { const index = count(i) let sum = 0 for (let j = 0; j < n; j++) { if (i & (1 << j)) sum += nums[j] } res[index].push(sum) }
return res
/** * @description * 二进制位1的个数 */ functioncount(num: number) { let res = 0 while (num) { num &= num - 1 res++ } return res } }
/** * @description * 单调不减的数组nums1和nums2分别找到两个数,其和与target的差最小 返回这个最小差值 */ functiontwoSum(nums1: number[], nums2: number[], target: number): number { let l = 0 let r = nums2.length - 1 let res = Infinity
while (l < nums1.length && r > -1) { const sum = nums1[l] + nums2[r] res = Math.min(res, Math.abs(target - sum)) if (sum === target) return0 elseif (sum > target) r-- else l++ }