字节KSUM一道你不知道的算法题

image

---

一.前言

---

文章主要给大家分享一个字节跳动自己出的算法题目--KSUM。作者学习了很多，但是没有能够很好的解决这个问题，只会用暴力回溯法解决。如果你有更好的办法，欢迎评论区发布出来让更多人看到，谢谢啦！

---

二. 有请主角--KSUM

---

题目

• 请用算法实现，从给定的无序、不重复的数组data中，取出K个数，找出K数之和和与输入的SUM相等的所有情况，并使算法的时间/空间复杂度尽量的低。

var ksum = function(data, k , sum){
}

• 思路
  对于这个题目作者可以想到的就是回溯法一步一步的尝试结果可不可以，流程如下：

1. 给定一个无重复数组[1,2,3,4,5,7],我们输入k为3，需要返回所有sum为10的情况。
2. 用回溯法，也就是暴力法，我来走一遍，首先选择第一个数，数组[1,2,3,4,5,7]中每一个数都可以被选到，如下图：

image

3. 第二步，我们可以以第一个数选择1为例，第二个数就可能选择[2,3,4,5,7]中的任何一个数，如下图：

image

4. 第三步：选择第三个数，这里我们以已经选择1和2为例第三个数就只能选择[3,4,5,7]，在选择第三数的时候，我们可以知道选择7是我们想要的结果，返回到结果的数组中，并退回上一步去找其他情况。如果第三步中都没有满足的数，也退回第二步去进行选择查找的可能的情况，当第二步都没有符合的情况，就再退回第一步进行查找直到所有的情况都遍历完，然后返回结果。

---

三.书写代码

我们以写js为例

上回溯模板

来自国外某大佬，凡是涉及回溯的都可以使用这个模板

/**
 * backtrack(){
 * if(){
 * //终止条件
 * }
 * 枚举出每一步可选的列表
 *  for(){
 *   //做出选择
 *     backtrack()
 *   // 撤销选择 回到上一步
 * }
 *
 * }
 */

开始解题

1. 初始化变量

var ksum = function(data, k , sum){
    let list = [];
    backtrack(data,list,k,sum)
    return list;
}

function backtrack(data, list, k, sum, tempList = [], start = 0){
}

2. 对数组进行遍历，选择

function backtrack(data, list, k, sum, tempList = [], start = 0){
    //tempList 已经做过的选择
    //for 枚举出每一步可选的列表
    for(let i = start; i<data.length;i++){
        //数组里面每一项都要选择
        tempList.push(data[i]);
        //之后的步骤
        backtrack(data, list, k, sum, tempList.slice(0), i+1)
        //tempList.slice(0)浅复制保存一下之前的结果，以防pop掉，之后返回空数组
        // 撤销上一步选择
        tempList.pop();
    }
}

首先做出选择，且每一项都会被选择，tempList暂存已经做的选择，start初始选择，且对起始位置进行限制（上一步走到哪里了）,i+1下一步的start

3. 终止条件

if(tempList.length === k ){
        if(tempList.reduce((a,b) => a+b,0) === sum){
            //找到
            list.push(tempList);
        }
        return;//回到上一步
    }

终止条件有两个，一是选择的数已经够了等于k，二是加起来的和等于sum，如果满足我们将暂存的数组，push到list结果里面，而且不管满不满足都回到上一步。

4. 书写完毕，测试
   所有代码如下：

var ksum = function (data, k, sum) {
    let list = [];
    backtrack(data, list, k, sum)
    return list;
}

function backtrack(data, list, k, sum, tempList = [], start = 0) {
    if (tempList.length === n) {
        if (tempList.reduce((a, b) => a + b, 0) === sum) {
            list.push(tempList);
        }
        return;
    }
    for (let i = start; i < data.length; i++) {
        tempList.push(data[i]);
        backtrack(data, list, k, sum, tempList.slice(0), i + 1)
        tempList.pop();
    }
}

console.log(ksum([1, 2, 3, 4, 5, 6, 7, 8], 3, 10))

结果：

image

结果正确，书写结束，模板真好用！！！

---

结束

文章看到现在也结束啦，如果有错误的话就麻烦大家给我指出来吧！如果觉得不错的话别忘了点个赞👍再走噢！欢迎把你想到的方法写在评论区喔，作者想要进步，哈哈。

个人博客地址

• 博客地址：小小洋的博客

期待

• 作者大三正在寻找春招实习中，期待大佬的青睐~