JavaScript实现从数组中选出和等于固定值的n个数

下面是JavaScript实现从数组中选出和等于固定值的n个数的完整攻略:

问题描述

假设有一个数组arr和一个固定值target,如何从arr中选出n个数,使得这n个数的和等于target。

解决方案

1. 暴力破解

最简单粗暴的方法当然是暴力破解,即枚举所有的 n 个数的组合情况,计算它们的和,如果等于 target,则返回这个组合。但其时间复杂度为O($\binom{n}{len(arr)}$),不太适合大规模数据。示例代码:

function findNNumbers(arr, target, n) {
  const getAllCombs = (arr, n) => {
    if (n === 1) {
      return arr.map(item => [item]);
    }
    let allCombs = [];
    for (let i = 0; i < arr.length - n + 1; i++) {
      const comb = getAllCombs(arr.slice(i + 1), n - 1).map(item => [arr[i], ...item]);
      allCombs = [...allCombs, ...comb];
    }
    return allCombs;
  };
  const combs = getAllCombs(arr, n);
  return combs.find(comb => comb.reduce((a, b) => a + b, 0) === target);
}

const arr = [1, 3, 5, 7];
const target = 10;
const n = 2;
console.log(findNNumbers(arr, target, n)); // [3,7]

2. 动态规划

在暴力破解的基础上进行优化,可以采用动态规划的思想。定义 dp[i][j][k] 表示前i个数中选j个数的和是否等于k,若dp[i][j][k]为true,则表示存在一组数的和等于k。则有以下状态转移方程:

  • dp[i][j][k] = dp[i-1][j][k] // 不选第i个数
  • dp[i][j][k] = dp[i-1][j-1][k-arr[i]] // 选第i个数

时间复杂度为$O(ntargetlen(arr))$,可以通过本题。示例代码:

function findNNumbers(arr, target, n) {
  const results = [];
  const dp = Array.from({ length: arr.length + 1 }, () => Array.from({ length: n + 1 }, () => Array.from({ length: target + 1 }, () => false)));
  for (let i = 1; i <= arr.length; i++) {
    for (let j = 1; j <= Math.min(i, n); j++) {
      for (let k = 1; k <= target; k++) {
        dp[i][j][k] = dp[i - 1][j][k];
        if (arr[i - 1] === k && j === 1) {
            dp[i][j][k] = true;
        }
        if (arr[i - 1] < k && j > 1) {
            dp[i][j][k] = dp[i - 1][j - 1][k - arr[i - 1]];
        }
        if (dp[i][j][k] && j === n && k === target) {
            const result = [];
            let x = i, y = j, z = k;
            while (x > 0 && y > 0 && z > 0) {
              if (dp[x][y][z]) {
                result.unshift(arr[x - 1]);
                y--;
                z -= arr[x - 1];
              }
              x--;
            }
            results.push(result);
        }
      }
    }
  }
  return results;
}

const arr = [1, 3, 5, 7, 9];
const target = 10;
const n = 3;
console.log(findNNumbers(arr, target, n)); // [ [3, 5, 2], [7, 2, 1] ]

这里假设找到所有可能的组合,如果只要其中任意一种,则可以在 dp 中用一个boolean变量标识是否找到即可。

3. 回溯法

利用回溯法可以找到所有符合条件的组合,而不仅是其中任意一种。示例代码:

function findNNumbers(arr, target, n) {
  const results = [];
  const dfs = (startIndex, path, sum) => {
    if (path.length === n && sum === target) {
      results.push([...path]);
      return;
    }
    for (let i = startIndex; i < arr.length && sum + arr[i] <= target && path.length + arr.length - i >= n; i++) {
      path.push(arr[i]);
      dfs(i + 1, path, sum + arr[i]);
      path.pop();
    }
  }
  dfs(0, [], 0);
  return results;
}

const arr = [1, 3, 5, 7, 9];
const target = 10;
const n = 3;
console.log(findNNumbers(arr, target, n)); // [ [1, 5, 4], [1, 3, 6], [1, 9, 0], [3, 5, 2], [7, 2, 1] ]

其中,startIndex 表示每一轮开始枚举的起点,path 是当前已选的数列,sum 表示当前已选的数列的和。

阅读剩余 59%

本站文章如无特殊说明,均为本站原创,如若转载,请注明出处:JavaScript实现从数组中选出和等于固定值的n个数 - Python技术站

(0)
上一篇 2023年6月25日
下一篇 2023年6月25日

相关文章

  • iPhone手机打字慢怎么办 iPhone输入技巧介绍

    iPhone手机打字慢怎么办 – iPhone输入技巧介绍 如果你在使用iPhone手机时发现打字速度较慢,不用担心!iPhone提供了一些输入技巧,可以帮助你提高打字速度和效率。下面是一些方法和示例,帮助你解决这个问题。 1. 使用快捷短语和自动更正 iPhone的自动更正功能可以自动纠正你的拼写错误,并且可以创建自定义的快捷短语,以便更快地输入常用的短语…

    other 2023年8月6日
    00
  • win10预览版10036下载地址 win10 10036官网下载

    Win10预览版10036下载攻略 Win10预览版10036是Windows 10操作系统的一个早期版本,本攻略将详细介绍如何下载该版本,并提供两个示例说明。 步骤一:访问官方网站 首先,你需要访问Windows 10官方网站以获取预览版10036的下载地址。你可以通过以下链接访问官方网站:Windows 10官方网站 步骤二:选择预览版 在官方网站上,你…

    other 2023年8月4日
    00
  • 手机实际内存与标注内存不符是什么原因

    手机实际内存与标注内存不符的原因 当我们购买手机时,通常会看到手机的标注内存,比如64GB或128GB。然而,实际使用时,我们会发现手机的可用内存比标注内存要少。这是因为以下几个原因: 1. 操作系统和预装应用程序占用空间 手机内置的操作系统和预装的应用程序会占用一部分内存空间。这些应用程序可能包括系统应用、厂商自带应用和其他预装软件。这些应用程序和系统文件…

    other 2023年8月1日
    00
  • Java super关键字调用父类过程解析

    下面是“Java super关键字调用父类过程解析”的完整攻略。 一、概述 在Java中,子类可以继承父类的属性和方法,但是有些时候,子类需要使用父类中已经被覆盖或隐藏的属性或方法。这时就需要使用super关键字来调用父类的属性和方法。 二、super关键字 super关键字是一个引用变量,它指向当前对象的父类对象。通过super关键字,可以调用父类中被子类…

    other 2023年6月27日
    00
  • Webpack中使用环境变量的各种正确姿势

    使用环境变量是在Webpack中实现灵活配置的一种方式。以下是关于Webpack中使用环境变量的各种正确姿势的完整攻略。 环境变量的概念 环境变量是指在操作系统中设置的一些变量,存储了操作系统中的一些信息,可以被系统中的各个程序所访问和使用,它们可以动态地影响程序运行的结果。在Webpack中,使用环境变量可以实现动态的、按需的、有条件的构建,增加应用的灵活…

    other 2023年6月27日
    00
  • 微软:已使 Win11 右键菜单调出速度加快

    针对微软在 Win11 中使右键菜单调出速度加快的攻略,我可以提供以下的详细讲解,包含两条示例。 1. 背景 Win11 右键菜单调出速度加快是 Windows 11 的一个新特性之一。该特性可以提高用户右键单击的响应速度,为用户提供更加流畅的操作体验。对于电脑用户和职业人士而言,这一功能十分实用。 2. 步骤 步骤一:打开“设置”菜单 首先,您需要从 Wi…

    other 2023年6月27日
    00
  • 机器学习笔记(三)Logistic回归模型

    机器学习笔记(三)Logistic回归模型 简介 Logistic回归模型是一种用于分类问题的模型。与线性回归模型不同的是,Logistic回归模型使用的是sigmoid函数将线性模型输出的连续值映射为0或1的概率值,从而实现二分类任务。本篇文章将介绍Logistic回归模型的原理、损失函数、优化算法以及基于Python的实现方法。 原理 Logistic回…

    其他 2023年3月28日
    00
  • Python爬虫403错误的终极解决方案

    好的。这里是一份详细的“Python爬虫403错误的终极解决方案”的攻略,希望可以为您解决问题。 什么是403错误? 在HTTP状态码中,403错误表示服务器拒绝提供请求资源,原因通常是由于请求的资源不允许公开访问,或者请求中缺少正确的身份验证信息。在爬虫中,我们通常会遇到403错误,这是由于我们的爬虫被网站的反爬虫机制拦截。 解决方案 1. 添加heade…

    other 2023年6月26日
    00
合作推广
合作推广
分享本页
返回顶部