java - 不同的Summands问题贪婪算法

我尝试用贪婪算法来解决不同的求和问题问题描述任务这个问题的目的是把一个给定的正整数_表示为多对的和。尽可能清楚的正整数。也就是说，要找到最大的 >，这样可以写成𝑘其中𝑛是正整数，𝑎1 + 𝑎2 + · · · + 𝑎𝑘表示所有𝑎1, . . . , 𝑎𝑘输入格式。输入由单个整数_组成。约束条件。𝑎𝑖 ̸= 𝑎𝑗。输出格式在第一行中，输出最大数1 ≤ 𝑖 < 𝑗 ≤ 𝑘.使1 ≤ 𝑛 ≤ 10^9可以表示为和。两个不同的正整数在第二行中，输出𝑘对不同的正整数总计为𝑛（如果有许多这样的表示，则输出其中任何一个）。我的代码：public class DifferentSummands { private static List<Integer> optimalSummands(int n) { List<Integer> summands = new ArrayList<Integer>(); int start = 1; int newNumber = n; if (n == 2) { summands.add(2); return summands; } while (true) { if (summands.contains(newNumber - start)) { start++; continue; } else { newNumber -= start; summands.add(start); start++; } if (newNumber == 0) { return summands; } } } public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int n = scanner.nextInt(); List<Integer> summands = optimalSummands(n); System.out.println(summands.size()); for (Integer summand : summands) { System.out.print(summand + " "); } }}如果输入太大，大约需要3.24秒，最长可用时间是1.5秒，我的代码就会失败。 (adsbygoogle = window.adsbygoogle || []).push({}); 最佳答案 对arraylist（summands变量）执行contains时，它会遍历列表中的所有值，以查找该项是否已经存在。O（n）操作。尝试使用哈希集而不是列表，以获得更好的性能o（1）。如果你关心结果中项目的顺序（总和），你可以使用LinkedHashSet。 (adsbygoogle = window.adsbygoogle || []).push({});