Open sisterAn opened 3 years ago
function numSum(nums, n, m) {
if (!nums.length || nums.length < n) return [];
nums = nums.sort((a, b) => a - b);
const result = [];
const stack = [];
const backtrace = (start) => {
if (stack.length === n - 1) {
let end = nums.length - 1;
while (start <= end) {
const temp = stack.reduce((acc, cur) => acc + cur);
if (temp + nums[start] === m) {
result.push([...stack, nums[start]]);
}
if (start !== end && temp + nums[end] === m) {
result.push([...stack, nums[end]]);
}
start++;
end--;
}
return;
}
for (let i = start; i < nums.length; i++) {
stack.push(nums[i]);
backtrace(i + 1);
stack.pop();
}
};
backtrace(0);
return result;
}
根据数组长度构建二进制数据,再选择其中满足条件的数据。
我们用 1
和 0
来表示数组中某位元素是否被选中。因此,可以用 0110
来表示数组中第 1
位和第 2
位被选中了。
所以,本题可以解读为:
N
。M
。我们的算法思路逐渐清晰起来: 遍历所有二进制,判断选中个数是否为 N
,然后再求对应的元素之和,看其是否为 M
。
例如:
var arr = [1, 2, 3, 4];
var N = 3;
var M = 6;
如何判断 N=3
是,对应的选取二进制中有几个 1
喃?
最简单的方式就是:
const n = num => num.toString(2).replace(/0/g, '').length
这里我们尝试使用一下位运算来解决本题,因为位运算是不需要编译的(位运算直接用二进制进行表示,省去了中间过程的各种复杂转换,提高了速度),肯定速度最快。
我们知道 1&0=0
、 1&1=1
,1111&1110=1110
,即 15&14=14
,所以我们每次 &
比自身小 1
的数都会消除一个 1
,所以这里建立一个迭代,通过统计消除的次数,就能确定最终有几个 1 了:
const n = num => {
let count = 0
while(num) {
num &= (num - 1)
count++
}
return count
}
现在最后一层判断就是选取的这些数字和必须等于 M
,即根据 N
生成的对应二进制所在元素上的和 是否为 M
比如 1110
,我们应该判断 arr[0] + arr[1] + arr[2]
是否为 M
。
那么问题也就转化成了如何判断数组下标是否在 1110
中呢?如何在则求和
其实也很简单,比如下标 1
在,而下标 3
不在。我们把 1
转化成 0100
, 1110 & 0100
为 0100
, 大于 0
,因此下标 1
在。而 1110 & 0001
为 0
,因此 下标 3
不在。
所以求和我们可以如下实现:
let arr = [1,2,3,4]
// i 为满足条件的二进制
let i = 0b1110
let s = 0, temp = []
let len = arr.length
for (let j = 0; j < len; j++) {
if ( i & 1 << (len - 1 - j)) {
s += arr[j]
temp.push(arr[j])
}
}
console.log(temp)
// => [1, 2, 3]
// 参数依次为目标数组、选取元素数目、目标和
const search = (arr, count, sum) => {
// 计算某选择情况下有几个 1,也就是选择元素的个数
const getCount = num => {
let count = 0
while(num) {
num &= (num - 1)
count++
}
return count
}
let len = arr.length, bit = 1 << len, res = []
// 遍历所有的选择情况
for(let i = 1; i < bit; i++){
// 满足选择的元素个数 === count
if(getCount(i) === count){
let s = 0, temp = []
// 每一种满足个数为 N 的选择情况下,继续判断是否满足 和为 M
for(let j = 0; j < len; j++){
// 建立映射,找出选择位上的元素
if(i & 1 << (len - 1 -j)) {
s += arr[j]
temp.push(arr[j])
}
}
// 如果这种选择情况满足和为 M
if(s === sum) {
res.push(temp)
}
}
}
return res
}
回溯的时间复杂度一般是O(n*n!)
/**
* 1. 可以使用指针等方法实现 之前在看代码随想录的时候已经实现过
* let arr = [1,4,7,11,9,8,10,6]
* let N = 3;
* let M = 27
*/
function findSum(arr, count, sum) {
const getCount = function (n) {
let count = 0;
while (n) {
n &= (n - 1)
count++
}
return count
}
let len = arr.length, bit = 1 << len
console.log('bit: ', parseInt(bit).toString(2));//bit: 1 0000 0000
let res = []
for (let i = 1; i < bit; i++) {
if (getCount(i) === count) {
let s = 0, temp = []
for (let j = 0; j < len; j++) {
//判断下标i是否在对应的二进制位置上
if (i & 1 << (len-1-j)) {
s += arr[j]
temp.push(arr[j])
}
}
if (s === sum) {
res.push(temp)
}
}
}
return res
}
let arr = [1, 4, 7, 11,9,8,10,6]
let N = 2;
let M = 5
console.log(findSum(arr, N, M))
let num = 1<<7
console.log(parseInt(num).toString(2))//10000000
function numSum(nums, n, m, arr = [], ans = [], index = 0) {
if(arr.length === n) return arr.reduce((a,b) => a + b, 0) === m && ans.push([...arr])
for(let i=index; i<nums.length; i++){
arr.push(nums[i])
numSum(nums, n, m, arr, ans, i + 1)
arr.pop()
}
return ans
}
function numSum(nums, n, m) {
if (!nums.length || !n || !m) return [];
let res = [], path = [], currentSum = 0;
let backtrace = (index) => {
if (path.length == n) {
if (currentSum === m) {
res.push([...path]); // 创建path的一个副本
}
return;
}
for (let i = index; i < nums.length; i++) {
path.push(nums[i]);
currentSum += nums[i]; // 更新当前路径和
backtrace(i + 1);
currentSum -= nums[i]; // 回溯时,恢复路径和
path.pop();
}
}
backtrace(0);
return res;
}
请用算法实现,从给定的无需、不重复的数组A中,取出N个数,使其相加和为M。并给出算法的时间、空间复杂度,如: