算法是抽象的概念，但越是抽象的东西，其越具有清晰的特征。特征如下：
确定性： 算法的每一个步骤都是明确的、可行的、结果可预期的
有穷性： 算法要有一个终止条件
输入和输出： 算法是用来解决问题的，少不了输入和输出
算法设计
这一块儿其实是很庞大的知识体系，需要苦练内功根基。下面简要介绍下算法设计方面的知识。
顺序执行、循环和分支跳转是程序设计的三大基本结构。
算法也是程序，千姿百态的算法也是由这三大基础结构构成的。
算法和数据结构关系紧密，数据结构是算法设计的基础。
如果对诸如哈希表、队列、树、图等数据结构有深刻的认识，那在算法设计上将会事半功倍。
上面提到的知识，主要的目的是抛砖引玉。算法的设计与分析是无上神功的心法口诀和入门要领。无论多么精妙绝伦的算法实现，都是由一些最基础的模型和范式组装起来的。
关于算法设计，这里给大家推荐一门课程，很不错，小伙伴可以看看：
算法设计与分析-Design and Analysis of Algorithms
降维分析，化繁为简
现在，到了最关键的时刻。我们回到题目中，开始设计我们的算法。
题干信息很简单，核心问题在于：
如何从数组中选取 N 个数进行求和运算。
如何做，这里我们通常且正确的做法，是对问题进行降维分析，并且化繁为简。
下面开始降维分析，化繁为简：
假如 N = 2 ，也就是找出数组中两个数的和为 M 的话，你会怎么做？可能你会想到每次从数组中弹出一个数，然后与余下的每个数进行相加，最后做判断。
那么问题来了，当 N = 3 呢，N = 10 呢，会发现运算量越来越大，之前的方式已经不可行了。
不妨换一种思路：
数组中选取不固定数值 N ，我们可以尝试着使用标记的方式，我们把 1 表示成选取状态， 把 0 表示成未选取状态。
假设数组 constarr=[1,2,3,4] ，对应着每个元素都有标记 0 或者 1 。如果 N=4 ，也就是在这个数组中，需要选择 4 个元素，那么对应的标记就只有一种可能 1111 ，如果 N=3 ，那就有 4 种可能，分别是 1110 、 1101 、1011以及 0111 (也就是 C4取3->4 ) 种可能。
开始抽象
通过上面的层层叙述，我们现在的问题可以抽象为：
标记中有几个 1 就是代表选取了几个数，然后再去遍历这些 1 所有可能存在的排列方式，最后做一个判断，这个判断就是：每一种排列方式，都代表着数组中不同位置的被选中的数的组合，所以这里就是将选中的这些数字，进行求和运算，然后判断求出的和是不是等于 M 。
于是，问题开始变得简单了。
如何将数组和标记关联
0101 这样的数据一眼望上去第一反应就是二进制啊
对于 arr 来说，有 4 个元素，对应的选择方式就是从 0000（ N = 0 ）到 1111( N = 4 )的所有可能。
而 1111 就是 15 的二进制，也就是说这所有的可能其实对应的就是 0 - 15 中所有数对应的二进制。
这里的问题最终变成了如何从数组长度 4 推导出 0 - 15
这里采用了位运算--左移运算， 1 << 4 的结果是 16 。
java实现方法如下：
import org.apache.commons.lang3.StringUtils;
import org.junit.Test;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;
/**
* @author zhengjimin
* @date 2021/2/26 下午2:46
* @function 整形数组，n、m
* 满足n个数之和等于m的，n个数的所有组合
*/
public class ArithTest {
@Test
public void test1(){
int[] arg = {1,2,3,4,5,6,7,8,9};
int n = 3;
int m = 12;
int size = arg.length;
List<String> listBinary = storeBinary(size);
List<int[]> list = new ArrayList<>();
List<String> sizeEqualN = listBinary.stream()
.filter(param->countN(param,n))
.collect(Collectors.toList());
sizeEqualN.stream()
.forEach(binary->{
int[] res = equalM(arg,binary,m);
if (res != null){
list.add(res);
}
});
}
@Test
public void test(){
int[] arg = {1,2,3,4,5};
int sum = Arrays.stream(arg).sum();
System.out.println(sum);
List<Integer> list = Arrays.stream(arg).boxed().collect(Collectors.toList());
long count = list.stream().count();
System.out.println(count);
}
private int[] equalM(int[] arg,String binary,int m){
int sum = 0;
List<Integer> list = new ArrayList<>();
for (int i = 0; i < binary.length(); i++) {
if (binary.charAt(i) == '1'){
sum += arg[i];
list.add(arg[i]);
}
}
if (sum == m){
System.out.println(list);
Integer[] toArray = list.toArray(new Integer[list.size()]);
return list.stream().mapToInt(Integer::intValue).toArray();
}
return null;
}
private boolean countN(String param,int n){
String rep = param.replaceAll("1","");
if (param.length() - rep.length() == n){
return true;
}
return false;
}
private List<String> storeBinary(int size){
List<String> listBinary = new ArrayList<>();
int count = 1<<size;
for (int i = 0; i < count; i++) {
String binary = pad0Right(i,size);
listBinary.add(binary);
}
return listBinary;
}
private String pad0Right(int i,int size){
String param = Integer.toBinaryString(i);
return StringUtils.leftPad(param,size,'0');
}
网友评论