PTA.7-6 数字拆分求和

题目

解题思路

这题目有两种思路：1. 利用等差数列公式 2. 暴力法
公式记不住，所以讲下暴力法（PTA对时间空间复杂度要求很低，LeetCode行不通的，还是要背公式）

暴力法很简单，就是穷举所有可能性。

• 枚举可能的序列首项 a1。
• 对于每个首项，构造从 a1 开始且相邻元素差值依次递增的序列，并检查该序列的和是否等于 k。
• 如果符合条件，则输出该序列。

具体步骤是：

首先假设序列的首项为 a1，然后依次构造出符合条件的序列。
对每个序列，依次加上差值 1、2、3、…，直到总和等于 k 或超出 k。
如果找到符合条件的序列，打印出来。

代码

import java.util.*;public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int k = sc.nextInt();findSequences(k);sc.close();}public static void findSequences(int k) {boolean findRes = false;//从1开始尝试for(int start = 1; start < k ; start++){//默认等差分布从1开始（题目规定）int difference = 1;int sum = 0;List<Integer> tmpList = new ArrayList<>();for(int num = start; sum < k; difference++){//更新总和sum += num;tmpList.add(num);//每次加一个等差分布值num += difference;if(sum == k){printSequence(tmpList, sum < k);findRes = true;break;}}}if(!findRes){System.out.println("");}}// 打印序列public static void printSequence(List<Integer> sequence, boolean end) {for (int i = 0; i < sequence.size(); i++) {if (i > 0) {System.out.print(",");}System.out.print(sequence.get(i));}if(!end){System.out.println();}}
}