一题算法|和为s的连续正数序列
2020/3/7 8:02:17
本文主要是介绍一题算法|和为s的连续正数序列,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
题目描述
输入一个正整数 target ,输出所有和为 target 的连续正整数序列(至少含有两个数)。
序列内的数字由小到大排列,不同序列按照首个数字从小到大排列。
题目示例
示例 1: 输入:target = 9 输出:[[2,3,4],[4,5]] 示例2: 输入:target = 15 输出:[[1,2,3,4,5],[4,5,6],[7,8]]
限制
- 1 <= target <= 10^5
题目要求连续两个以上的正整数之后等于给定的值,这题有两种解法,一种是枚举,一种是利用等差数列求和的方法来解决这个问题。
解法一:枚举
枚举方法就是利用双层遍历,第一层遍历的终止条件为给定值的一半,例如给定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。等差数列求和可以减少遍历项,从而提高效率。
求和方法会出现三种情况:
- sum = target,说明区间[n,m]是一个解
- sum > target,说明区间[n,m]不是一个解,这是需要将首项n 往后移动一位来减少区间的项数,从而减少 sum 的值。
- sum < target,说明区间[n,m]不是一个解,这种情况下需要将尾项 m 向后移动一位,来扩大区间的项数,增大sum 的值。
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)
作者:平头哥,学会伺机而动,实现弯道超车
这篇关于一题算法|和为s的连续正数序列的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-10-01基于Python+Vue开发的医院门诊预约挂号系统
- 2024-10-01基于Python+Vue开发的旅游景区管理系统
- 2024-10-01RestfulAPI入门指南:打造简单易懂的API接口
- 2024-10-01初学者指南:了解和使用Server Action
- 2024-10-01Server Component入门指南:搭建与配置详解
- 2024-10-01React 中使用 useRequest 实现数据请求
- 2024-10-01使用 golang 将ETH账户的资产平均分散到其他账户
- 2024-10-01JWT用户校验课程:从入门到实践
- 2024-10-01Server Component课程入门指南
- 2024-09-30Dnd-Kit学习:新手快速入门指南