数组中找出n个数相加，最接近num的

偏执的太偏执、 2022-12-22 09:15 156阅读 0赞

# 数学问题 -  数组中找出n个数相加，最接近num的 #

有同事提过这个问题，现在有时间了实现下做个整理，主要当时排列组合的概念都不知道是啥了，更不用说实现功能了。

已经不知道排列组合，二项式定理，集合的可以先复习下相关概念和公式算法。

[java实现排列组合  ][java][https://blog.csdn.net/xinpz/article/details/109728624][java]

--------------------

**目录**

数学问题 -  数组中找出n个数相加，最接近num的

一、概述

二、示例代码

--------------------

## 一、概述 ##

问题：数组中找出n个数相加，最接近num的

实现思路：

1、核心算法是对数组做组合，然后记录枚举

2、对组合枚举记录加和，和比较值num做减法取绝对值。

3、用map<Integer,List<String>> 做结果集。key为组合枚举记录加和，和比较值num做减法取的绝对值。 value为组合枚举记录。由于接近的记录会有多个，所以用list。

4、对map的key排序取最小值，value就是想要的结果。

--------------------

## 二、示例代码 ##

package com.cnzz.mytest.test;
    
    import lombok.extern.slf4j.Slf4j;
    import org.junit.Test;
    
    import java.util.*;
    import java.util.concurrent.atomic.AtomicReference;
    import java.util.stream.Collectors;
    
    /**
     * ************************************************************
     * Copyright © 2020 cnzz Inc.All rights reserved.  *    **
     * ************************************************************
     *
     * @program: demo
     * @description:
     * @author: cnzz
     * @create: 2020-10-28 19:14
     **/
    @Slf4j
    public class ArrayCalculation {
    
        private static String SPLIT = "+";
        private static String ES = "=";
        //组合算法全局区间
        static List<Integer> list = new ArrayList<>();
        //组合枚举数记录
        static int cnt = 0;
    
        @Test
        public void excute() {
    
            int amt = 4;//数组数目 --用于生成数组
            int max = 10;//数值边界 --用于生成数组
            boolean isDeduplication = true;//是否数组去重 --用于生成数组
    
            // 比较值
            int num = 14;
    
            //获取数组--用于生成数组
            int[] array = getRandomArray(amt, max, isDeduplication);
    
            //找出数组中 几个数之和最靠近 num 的
            List<String> result = arrayCalculation(array, num);
            //结果打印
            log.info("找出数组中几个数之和最靠近num的|数组{},比较值{}", array, num);
            result.parallelStream().forEach(log::info);
        }
    
        /**
         * 找出数组中 几个数之和最靠近 num 的
         * <p>
         * 1、剔除数组中大于num的
         * 2、组合枚举记录 Map<Integer, List<String>>
         * 3、map的key排序，获取最小
         * 4、找出最小的n个记录获取返回
         *
         * @param array
         * @param num
         */
        public List<String> arrayCalculation(int[] array, int num) {
    
            //1、剔除数组中大于num的
            //array = getSmallArray(array, num);
            //log.info("剔除数组中大于num的|数组{}", array);
    
            //二项式定理计算组合枚举个数
            int count = (int) Math.pow(2, array.length) - 1;
            log.info("非空子集数{}", count);
    
            //2、非空子集，组合加和并记录 map<int,list<String>>
            Map<Integer, List<String>> integerListMap = appendList(array, num);
            log.info("组合枚举数{}", cnt);
    
            //3、map的key排序，获取最小,map取第一个key
            Integer smallKey = getSmallKey(integerListMap);
            log.info("最小差值{}", smallKey);
    
            return integerListMap.get(smallKey);
        }
    
        /**
         * 组合
         *
         * @param array 数组全集
         * @param num   标准值
         */
        private Map<Integer, List<String>> appendList(int[] array, Integer num) {
            Map<Integer, List<String>> paMap = new HashMap<>();
            //组合逻辑，1-n的组合
            for (int i = 0; i < array.length; i++) {
                recursion3(array, 0, i + 1, 0, paMap, num);
            }
            return paMap;
        }
    
        /**
         * 对map的key排序获取最小
         *
         * @param integerListMap map Map<Integer, List<String>>
         * @return Integer map中最小的key
         */
        private Integer getSmallKey(Map<Integer, List<String>> integerListMap) {
            List<Integer> keyList = new ArrayList<>();
            Iterator<Integer> iterator = integerListMap.keySet().iterator();
            while (iterator.hasNext()) {
                keyList.add(iterator.next());
            }
            Collections.sort(keyList);
            return keyList.get(0);
        }
    
    
        /**
         * 组合并枚举-递归
         * 核心算法
         *
         * @param array    数组
         * @param curnum   栈中当前个数
         * @param maxnum   最大位数
         * @param indexnum 当前下标
         * @param paMap    结果map  -枚举记录用到
         * @param num      比较值  -枚举记录用到
         */
        public void recursion3(int[] array, int curnum, int maxnum, int indexnum, Map<Integer, List<String>> paMap, Integer num) {
            if (curnum == maxnum) {
                cnt++;
                AtomicReference<String> str = new AtomicReference<>(new String());
                list.forEach(item -> {
                    str.set(str + SPLIT + item);
                });
                addResultMap(paMap, num, str.get().substring(1, str.get().length()));
                return;
            }
            for (int i = indexnum; i < array.length; i++) {
                if (!list.contains(array[i])) {
                    list.add(array[i]);
                    recursion3(array, curnum + 1, maxnum, i, paMap, num);
                    list.remove(new Integer(array[i]));
                }
            }
        }
    
    
        /**
         * 组合记录保存结果集
         *
         * @param paMap 结果集
         * @param num   比较值
         * @param str   组合枚举记录
         */
        private void addResultMap(Map<Integer, List<String>> paMap, Integer num, String str) {
            String[] idsArry = str.split("\\+");
            List<Integer> listSec = Arrays.stream(idsArry)
                    .map(s -> Integer.parseInt(s.trim()))
                    .collect(Collectors.toList());
            Integer sum2 = listSec.stream().reduce(Integer::sum).orElse(0);
            Integer strKey2 = Math.abs(num - sum2);
            pushMap(paMap, str, strKey2, sum2);
        }
    
        /**
         * 填充map
         *
         * @param paMap  map结果集
         * @param str    组合枚举记录
         * @param strKey key绝对值
         * @param sum    记录和
         */
        private void pushMap(Map<Integer, List<String>> paMap, String str, Integer strKey, Integer sum) {
            String record = sum + ES + str;
            log.debug("组合记录枚举|{}", record);
            if (paMap.get(strKey) == null) {
                List<String> strList = new ArrayList<>();
                strList.add(record);
                paMap.put(strKey, strList);
            } else {
                List<String> strings = paMap.get(strKey);
                strings.add(record);
                paMap.put(strKey, strings);
            }
        }
    
    
        /**
         * 获取随机数组
         *
         * @param amt             数目
         * @param max             最大范围
         * @param isDeduplication 去重
         * @return int[]
         */
        private int[] getRandomArray(int amt, int max, boolean isDeduplication) {
            log.info("随机获取数据|数目{},范围{},去重{}", amt, max, isDeduplication);
            List<Integer> list = new ArrayList<>();
            for (int i = 0; i < amt; i++) {
                Integer num = getRandomNum(max, isDeduplication, list);
                list.add(num);
            }
            int[] ints = list.stream().mapToInt(Integer::valueOf).toArray();
            log.info("获取的数组{}", ints);
            return ints;
        }
    
        /**
         * 获取随机数
         * -递归，不重复的返回
         *
         * @param max             边界值
         * @param isDeduplication 是否去重
         * @param list            原list
         * @return 随机数
         */
        private Integer getRandomNum(int max, boolean isDeduplication, List<Integer> list) {
            Integer num = (int) (Math.random() * (max-1)+1);
            if (isDeduplication && list.contains(num)) {
                return getRandomNum(max, isDeduplication, list);
            } else {
                return num;
            }
        }
    
        /**
         * 剔除数组中大于num的
         *
         * @param array 原数组
         * @param num   边界值
         * @return 数组
         */
        public static int[] getSmallArray(int[] array, int num) {
    
            // int[] 转 List<Integer>
            List<Integer> list = Arrays.stream(array).boxed().collect(Collectors.toList());
            // Arrays.stream(arr) 可以替换成IntStream.of(arr)。
            // 1.使用Arrays.stream将int[]转换成IntStream。
            // 2.使用IntStream中的boxed()装箱。将IntStream转换成Stream<Integer>。
            // 3.使用Stream的collect()，将Stream<T>转换成List<T>，因此正是List<Integer>。
    
            Iterator<Integer> iterator = list.iterator();
    
            while (iterator.hasNext()) {
                if (num < iterator.next().intValue()) {
                    iterator.remove();
                }
            }
    
            int[] arr1 = list.stream().mapToInt(Integer::valueOf).toArray();
            // 想要转换成int[]类型，就得先转成IntStream。
            // 这里就通过mapToInt()把Stream<Integer>调用Integer::valueOf来转成IntStream
            // 而IntStream中默认toArray()转成int[]。
            return arr1;
        }
    }

--------------------

测试结果打印

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpbnB6_size_16_color_FFFFFF_t_70][]

--------------------

总结：

数学还是很重要的，，，

[java]: https://blog.csdn.net/xinpz/article/details/109728624
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpbnB6_size_16_color_FFFFFF_t_70]: /images/20221120/0bb0a895c8c54a5688778d42ef715787.png