算法题-相加为目标数:和两数:和、三数:和、从数组取n个数相加为m不可重复取、从数组取任意个数相加为m可重复取

目录

相加为目标数之和

题目

两数之和

三数之和

原题链接

解析

核心思想

答案

从数组中取n个数相加为m（不可重复取）

解析 

核心思想

答案

从数组中取任意个数相加为m（可重复取）

解析

核心思想

答案

---

相加为目标数之和

当为两数、三数之和时，可以通过取出一个数和目标值的差去解决问题，通常会用到hash、双指针等算法去优化题解。

当为多数之和时，我们可以采取递归的方法，把n个数和拆为n-1个数和与剩余的一个数去递归。或者用动态规范的方法，找到res[i]的解和res[i-arr[j]]的关系（j表示的是数组中的每一位）

最后需要注意在求解的时候是否会有重复的解集存在。

题目

两数之和

三数之和

给出一个有n个元素的数组S，S中是否有元素a,b,c满足a b c=0？找出数组S中所有满足条件的三元组。

1. 三元组（a、b、c）中的元素必须按非降序排列。（即a≤b≤c）
2. 解集中不能包含重复的三元组。

示例：给定的数组 S = {-10 0 10 20 -10 -40},解集为(-10, -10, 20),(-10, 0, 10)

输入：[0]

返回值：[]

输入：[0,0,0]

返回值：[[0,0,0]]

输入：[-2,0,1,1,2]

返回值：[[-2,0,2],[-2,1,1]]

输入：[-10,0,10,20,-10,-40]

返回值：[[-10,-10,20],[-10,0,10]]

原题链接

三数之和_牛客题霸_牛客网

解析

注意第二个示例，输入3个零返回的数组中由零构成，上面的不包含重复的三元组是指的数组中的每一位在一个解集中只可以出现1次，但数字时可以相同的。

核心思想

采用双指针的算法，首先固定一位，左右指针从两端开始，向内收紧结束，当有和为固定的数的相反数的加入解集。

固定的这一位从数组0~len-2，双指针一直在固定位的右端，这样能方便计算。

答案

1.  
   function threeSum(num) {
2.  
   num.sort((a, b) => a - b)
3.  
   let len = num.length
4.  
   let res = []
5.  
   if (len < 3) {
6.  
   return res
7.  
   }
8.  
   for (let i = 0; i < len - 2; i ) {
9.  
   while (num[i] == num[i - 1]) {
10.  
    i
11.  
    }
12.  
    let left = i 1, right = len - 1
13.  
    while (left < right) {
14.  
    let sum = num[i] num[left] num[right]
15.  
    if (sum === 0) {
16.  
    res.push([num[i], num[left], num[right]])
17.  
    right--
18.  
    left
19.  
    while (num[left] == num[left - 1]) {
20.  
    left
21.  
    }
22.  
    while (num[right] == num[right 1]) {
23.  
    right--
24.  
    }
25.  
    } else if (sum < 0) {
26.  
    left
27.  
    } else {
28.  
    right--
29.  
    }
30.  
    }
31.  
    }
32.  
    return res
33.  
    }

从数组中取n个数相加为m（不可重复取）

请用算法实现，从给定的不重复的数组中，取出n个数，使其相加和为m，如：

1.  
   let arr = [1, 4, 7, 11, 9, 8, 10, 6]
2.  
   let n = 3
3.  
   let m = 27
4.  
   Result:
5.  
   [[7,11,9],[11,10,6],[9,8,10]]

解析 

注意该题答案不能直接用于上题三数之和，因为给的数组是不重复的，当nums([-2,0,0,2,2],3,0)会返回[[-2,0,2],[-2,0,2]]。得到重复的答案。

核心思想

把n个数和拆为n-1个数和与剩余的一个数。

backtrace(start)表示从start-length-1的nums数组中选n为数和为m。

stack数组中为已经选取了的数。

剩余的这个数可能是每一位，故for循环将数组的每一位放入stack中调用backtrace函数，由于每次将一位放入了数组，故需要取出（这里注意的是递归中每次也会调用push和pop，所以for循环时，最外层每次的stack数组会为空）。

最后寻找出口：当放入stack中的数为n-1时，表示只用寻找一个数了。

答案

1.  
   function numsSum(nums, n, m) {
2.  
   if (!nums.length || nums.length < n) return [];
3.  
   nums.sort((a, b) => a - b)
4.  
   const result = [];
5.  
   const stack = []
6.  
   const backtrace = (start) => {
7.  
   if (stack.length === n - 1) {
8.  
   const temp = stack.reduce((acc, cur) => acc cur);
9.  
   if(nums.slice(start).includes(m-temp)){
10.  
    result.push([...stack,m-temp])
11.  
    }
12.  
    return
13.  
    }
14.  
    for (let i = start; i < nums.length; i ) {
15.  
    stack.push(nums[i])
16.  
    backtrace(i 1)
17.  
    stack.pop()
18.  
    }
19.  
    }
20.  
    backtrace(0)
21.  
    return result
22.  
    }

从数组中取任意个数相加为m（可重复取）

从数组中选取任意个数的数可以重复相加为target，输出所有的组合，不要求组合中的顺序，

例如[1,2,3]，target=4,输出[[1,1,1,1],[1,1,2],[1,3],[2,2]]。

解析

注意是可重复选取，故可能存在重复的解，故最后需要去重。

核心思想

递归：

把n个数和拆为n-1个数和与剩余的一个数。

首先确定入参和出参，入参f(arr,target)，出参result数组。

确定上下层级的关系，f(arr,target)=选中的1位和剩下的n-1位返回的result的拼接数组即f(arr,target-arr[i])，i从0~length-1。

找出口，当target-arr[i]===0时，存入result中，大于0时不进行操作。

动态规划：

赋初始值：小于数组中最小值的，res解集为空，

找到res[i]下层之间的关系：res[i]=对数组的每一位进行循环(j)，如果res[i-arr[j]]的数组有解就将该解和arr[j]合并，还需要判断右直接等于arr[j]的也加入。

答案

方法一（递归） 

1.  
   function join(a, arr) {
2.  
   return arr.map(v => {
3.  
   v.push(a)
4.  
   return v
5.  
   })
6.  
   }
7.  
   function find(arr, target) {
8.  
   arr = arr.sort((a, b) => a - b).filter(v => v <= target)
9.  
   if (!arr.length) {
10.  
    return;
11.  
    }
12.  
    let result = []
13.  
    for (let i = 0; i < arr.length; i ) {
14.  
    if (target - arr[i] > 0) {
15.  
    result.push(...join(arr[i], find(arr, target - arr[i])))
16.  
    }
17.  
    if (target - arr[i] === 0) {
18.  
    result.push([arr[i]])
19.  
    }
20.  
    }
21.  
    return result
22.  
    }
23.  
    let result = find([1, 2, 3, 4], 6)
24.  
    console.log([...new Set(result.map((v) => v.sort((a, b) => a - b).join('')))].map((v) => v.split('').map(v => Number(v))))

方法二（动态规划） 

1.  
   function find(arr, target) {
2.  
   function join(a, arr) {
3.  
   return JSON.parse(JSON.stringify(arr)).map(v => {
4.  
   v.push(a)
5.  
   return v
6.  
   })
7.  
   }
8.  
   let result = []
9.  
   arr = arr.sort((a, b) => a - b).filter(v => v <= target)
10.  
    for (let i = 0; i <= target; i ) {
11.  
    if (i < arr[0]) {
12.  
    result[i] = []
13.  
    } else {
14.  
    result[i] = []
15.  
    for (let j = 0; j < arr.length; j ) {
16.  
    if (i>arr[j] && result[i - arr[j]].length) {
17.  
    result[i].push(...join(arr[j], result[i - arr[j]]))
18.  
    }
19.  
    if(i===arr[j]){
20.  
    result[i].push([i])
21.  
    }
22.  
     
23.  
    }
24.  
    }
25.  
    }
26.  
    return [...new Set(result.pop().map((v)=>v.sort((a,b)=>a-b).join('')))].map((v)=>v.split('').map(v=>Number(v)))
27.  
    }
28.  
    console.log(find([2,3,4],6))

这篇好文章是转载于：学新通技术网