输入一个正整数 target ,输出所有和为 target 的连续正整数序列(至少含有两个数)。
序列内的数字由小到大排列,不同序列按照首个数字从小到大排列。
示例 1: 输入:target = 9 输出:[[2,3,4],[4,5]] 示例2: 输入:target = 15 输出:[[1,2,3,4,5],[4,5,6],[7,8]]
限制
题目要求连续两个以上的正整数之后等于给定的值,这题有两种解法,一种是枚举,一种是利用等差数列求和的方法来解决这个问题。
枚举方法就是利用双层遍历,第一层遍历的终止条件为给定值的一半,例如给定target=15,那么第一层的终止条件为7.5,第二层的终止条件为连续数之和大于target。
1、解题代码:
class Solution { public int[][] findContinuousSequence(int target) { // 存放最终的结果集 List<int[]> result = new ArrayList<>(); // 遍历总和 int sum = 0; // 枚举 for (int i = 1; i <= target / 2; i++) { for (int j = i; ; j++) { sum += j; // 如果sum 大于 target 直接返回 if(sum > target) { sum = 0; break; } if (sum == target){ // 枚举 n 到 m 之间的元素 int[] temp = new int[j - i + 1]; int n = i; for (int x = 0; x < temp.length; x++) { // 题目有要求 按照从小到大的顺序排列 temp[x] = n; n++; } result.add(temp); break; } } } return result.toArray(new int[0][]); } }
复杂度分析
时间复杂度:需要遍历一次数组,所以时间复杂度是O(N^2)
空间复杂度:在这个过程中使用到临时数组,理论上这个临时数组无限的啊,所以空间复杂度为O(N)
连续正整数之和,可以利用等差数列求和来解决,等差数列求和公式为:sum=((n+m)*(m-n+1))/2。等差数列求和可以减少遍历项,从而提高效率。
求和方法会出现三种情况:
1、解题代码
class Solution { public int[][] findContinuousSequence(int target) { // 存放最终的结果集 List<int[]> result = new ArrayList<>(); // n:低位数字 m:高位数字 int n = 1, m = 2; /** * sum < target 的话,说明m可以往后移动,来增大sum * * sum > target 的话,需要n往后移动来减少元素个数,减少sum的值 * * sum = target 的话,把 n 到 m 之间的数枚举出来 * * 结束条件为 n< m */ while (n < m) { // 等差数列求和 int sum = ((n + m) * (m - n + 1)) / 2; if (sum == target) { // 枚举 n 到 m 之间的元素 int[] temp = new int[m - n + 1]; int j = n; for (int i = 0; i < temp.length; i++) { temp[i] = j; j++; } result.add(temp); // 前指针向前移动 n++; } else if (sum < target) { m++; } else { n++; } } return result.toArray(new int[0][0]); } }
复杂度分析
时间复杂度:需要遍历一次数组,所以时间复杂度是O(N)
空间复杂度:在这个过程中使用到临时数组,理论上这个临时数组无限的啊,所以空间复杂度为O(N)
这两种解法根据 leetcode 上的提交结果来看,性能和效率上相差不大,但是求和法相对稳定。
以上就是我的两种解法,不知道小伙伴们是如何解这题的,欢迎在留言区亮出你的解法。
互联网平头哥(id:pingtouge_java)
作者:平头哥,学会伺机而动,实现弯道超车