小明很喜欢数学,有一天他在做数学作业时,要求计算出9~16的和,他马上就写出了正确答案是100。但是他并不满足于此,他在想究竟有多少种连续的正数序列的和为100(至少包括两个数)。没多久,他就得到另一组连续正数和为100的序列:18,19,20,21,22。现在把问题交给你,你能不能也很快的找出所有和为S的连续正数序列?
数据范围：
进阶：时间复杂度)
进阶：时间复杂度
[编程题]和为S的连续正数序列
前缀合
public ArrayList<ArrayList<Integer>> FindContinuousSequence (int sum) {
ArrayList<ArrayList<Integer>> res = new ArrayList<>();
if(sum == 0) return res;
Map<Integer,Integer> map = new HashMap<>();
map.put(0,0);//当前的和，当前的值
int cursum = 0;
for(int i=1;i<sum;i++){
cursum+=i;
map.put(cursum,i);
if(map.containsKey(cursum-sum)){
int end = map.get(cursum);
int start = map.get(cursum-sum);
ArrayList<Integer> path = new ArrayList<>();
for(int j = start+1;j<=end;j++) path.add(j);
res.add(path);
}
}
return res;
}
}
发表于 2024-06-15 09:15:00
回复(0)
import java.util.*;
public class Solution {
/**
*思路：使用双层for循环，外层循环从i = 1开始，内层循环开始从j = i+1，
然后计算连续的和是否为sum，如果为sum则保存数组
*/
public ArrayList<ArrayList<Integer>> FindContinuousSequence (int sum) {
// write code here
if (sum == 0) return new ArrayList<>();
int count = 0;
ArrayList<ArrayList<Integer>> arrayLists = new ArrayList<>();
for (int i = 1; i < sum; i++) {
ArrayList<Integer> arr = new ArrayList<>();
arr.add(i);
count = i;
for (int j = i + 1; j < sum; j++) {
count += j;
arr.add(j);
if (count > sum) break;
if (count == sum) {
arrayLists.add(arr);
break;
}
}
}
return arrayLists;
}
}
发表于 2023-09-07 15:31:34
回复(0)
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param sum int整型
* @return int整型ArrayList<ArrayList<>>
*/
public ArrayList<ArrayList<Integer>> FindContinuousSequence (int sum) {
// write code here
ArrayList<ArrayList<Integer>> list = new ArrayList<ArrayList<Integer>>();
//遍历临界点判断(sum/i)-i/2>0,假设平均数为sum/i，假设第一个正数为(sum/i)-i/2，则正数>0,化简后i*i<2*sum
for (int i = 2; i * i < 2 * sum; i++) {
int start = -1;
if (i >> 1 << 1 == i) {
int n = sum % (i / 2);
if (n == 0) {
int k = sum / (i / 2);
if (k != (k >> 1 << 1)) {
int j = (k - 1) / 2;
start = j - i / 2 + 1;
}
}
} else {
if (sum % i == 0) {
int j = sum / i;
start = j - i / 2 ;
}
}
if (start >= 0) {
ArrayList<Integer> nums = new ArrayList<Integer>();
for (int l = 0; l < i; l++) {
nums.add(start++);
}
list.add(nums);
}
}
list.sort(new Comparator<ArrayList<Integer>>() {
@Override
public int compare(ArrayList<Integer> integers, ArrayList<Integer> t1) {
return integers.get(0) - t1.get(0);
}
});
return list;
}
}
发表于 2023-08-31 19:17:19
回复(0)
import java.util.ArrayList;
public class Solution {
public ArrayList<ArrayList<Integer> > FindContinuousSequence(int sum) {
ArrayList<ArrayList<Integer> > ans =new ArrayList<>();
ArrayList<Integer> per = new ArrayList<>();
if(sum == 0 || sum == 1) return ans;
int[] arr = new int[sum / 2 + 2];
for(int i = 0; i <= sum / 2 + 1; i++){
arr[i] = i + 1;
}
int left = 0;
int right =0;
int n = arr.length;
while(left < arr.length && right < arr.length){
if(Sum_arr(arr , left , right) < sum){
right++;
}
else if(Sum_arr(arr , left , right) > sum){
left++;
}
else if(Sum_arr(arr , left , right) == sum){
for(int i = left; i <= right; i++)
per.add(arr[i]);
ans.add(per);
per = new ArrayList<>();
right++;
left++;
}
if(left == right) right++;
}
return ans;
}
public int Sum_arr(int[] arr, int left, int right){
int s = 0;
for(int i = left; i <= right; i++)
s += arr[i];
return s;
}
}
发表于 2023-03-08 20:52:39
回复(0)
import java.util.ArrayList;
public class Solution {
public ArrayList<ArrayList<Integer> > FindContinuousSequence(int sum) {
ArrayList<ArrayList<Integer>> target=new ArrayList<>();
int count=2;
while(sum/count-((count-1)/2)>0){
//当份数为偶数，却有中间数的时候
if(count%2==0 && sum%count==0){
count++;
continue;
}
//当份数为奇数，却没有中间数的时候 continue
if(count%2!=0 && sum%count!=0){
count++;
continue;
}
//否则的话有戏
int start=(sum/count)-(count-1)/2;
ArrayList<Integer> temp=new ArrayList<>();
int ssum=0;
for(int i=start;i<start+count;i++){
ssum+=i;
temp.add(i);
}
//判断和是否正确
if(ssum==sum)
target.add(0,temp);
count++;
}
return target;
}
}
发表于 2022-08-10 10:32:44
回复(0)
import java.util.ArrayList;
public class Solution {
public ArrayList<ArrayList<Integer> > FindContinuousSequence(int sum) {
ArrayList<ArrayList<Integer> > result = new ArrayList<ArrayList<Integer> >();
if (sum == 0 || sum == 1 || sum == 2) {
return result;
}
for (int i = 1; i < sum; i++) {
Double x = (1-2*i+Math.sqrt(Math.pow(2*i-1,2)+8*sum))/2;
if (x > x.intValue()) {
continue;
}
ArrayList<Integer> list = new ArrayList<Integer>();
for (int j = i; j < i+x.intValue(); j++) {
list.add(j);
}
result.add(list);
}
return result;
}
}
基于等差数列性质，判断方程是否有整数解即可
发表于 2022-08-07 18:03:18
回复(0)
// 滑动窗口
public ArrayList<ArrayList<Integer> > FindContinuousSequence(int sum) {
ArrayList<ArrayList<Integer>> res = new ArrayList<>();
if(sum == 0){
return res;
}
int[] arr = new int[sum-1];
for (int i = 0; i < arr.length; i++) {
arr[i] = i+1;
}
int left = 0;
int right = 0;
int cur = 0;
ArrayList<Integer> temp;
while(right < arr.length){
cur += arr[right];
while(cur > sum){
cur = cur - arr[left];
left++;
}
if (cur == sum){
temp = new ArrayList<>();
for (int i = left;i<=right;i++){
temp.add(arr[i]);
}
res.add(temp);
}
right ++;
}
return res;
}
发表于 2022-06-11 08:07:56
回复(0)
import java.util.ArrayList;
public class Solution {
public ArrayList<ArrayList<Integer> > FindContinuousSequence(int sum) {
ArrayList<ArrayList<Integer>> ans = new ArrayList<>();
int low = 1;
int high = 2;
while (low < high) {
int total = ((low + high) * (high - low + 1)) / 2;
if (total == sum) {
ArrayList<Integer> tmp = new ArrayList<>();
for (int i = low; i <= high; i++) {
tmp.add(i);
}
ans.add(tmp);
low++;
} else if (total < sum) {
high++;
}else {
low++;
}
}
return ans;
}
}
发表于 2022-05-29 11:14:20
回复(0)
滑动窗口
import java.util.ArrayList;
public class Solution {
public ArrayList<ArrayList<Integer> > FindContinuousSequence(int sum) {
ArrayList<ArrayList<Integer>> res = new ArrayList<>();
int left = 1, right = 2; // 连续正数
while(right < sum) { // 相当于尝试以left这个数作为区间起点，能不能找到一个和为s的连续正数序列
int total = 0;
while((total = getTotal(left, right)) > sum) { // 大了，说明以left作为起点是拿不到结果的，所以收缩左边界
left++;
}
if(total == sum) { // 收集结果
ArrayList<Integer> one = new ArrayList<>(right - left + 1);
for(int i = left; i <= right; i++) {
one.add(i);
}
res.add(one);
left++; // 收集结果后，左边界就要右移了，虽然不移动也行，因为前面有一个while兜底了
}
right++; // 扩张右边界
}
return res;
}
private int getTotal(int left, int right) {
return (left + right) * (right - left + 1) / 2;
}
}
发表于 2022-05-25 11:14:29
回复(0)
import java.util.ArrayList;
public class Solution {
public ArrayList<ArrayList<Integer> > FindContinuousSequence(int sum) {
ArrayList<ArrayList<Integer>> lists = new ArrayList<ArrayList<Integer>>();
if(sum <= 2){
return lists;
}
for(int i = 1; i <= sum/2 + 1 ; i++){
int result = 0;
ArrayList<Integer> list = new ArrayList<Integer>();
for(int j = i; j <= sum/2 + 1 ; j++){
result += j;
list.add(j);
if(result == sum){
lists.add(list);
break;
}else if(result > sum){
break;
}
}
}
return lists;
}
}
发表于 2022-05-17 19:50:27
回复(0)
public ArrayList<ArrayList<Integer>> FindContinuousSequence(int sum) {
// 返回多个连续正数序列，ret 是 list 的 list
ArrayList<ArrayList<Integer>> ret = new ArrayList<>();
// 当前和从3(1 + 2)开始，低于的直接返回空ret
int start = 1, end = 2, curSum = 3;
// end指针没走到单独数字sum时
while (end < sum) {
if (curSum > sum) {
// 当前和比要求的sum大，curSum吐出start来，start右移
curSum -= start;
start++;
} else if (curSum < sum) {
// 当前和没要求的sum大，end指针右移，curSum把它吃进来
end++;
curSum += end;
} else {
// 正好相等时
ArrayList<Integer> list = new ArrayList<>();
for (int i = start; i <= end; i++) {
// 构造这段连续数序列
list.add(i);
}
// 把序列存入序列的list
ret.add(list);
// 开始下一段旅程
// urSum吐出start来，start右移
curSum -= start;
start++;
// end指针右移，curSum把它吃进来
end++;
curSum += end;
}
}
return ret;
}
借鉴别的大佬的思考，自己做了笔记。分享给大家
发表于 2022-03-19 10:50:37
回复(0)
import java.util.ArrayList;
public class Solution {
public ArrayList<ArrayList<Integer> > FindContinuousSequence(int sum) {
ArrayList<ArrayList<Integer>> ret = new ArrayList();
if(sum <= 1){
return ret;
}
int mid = (sum+1)>>1;
int count = 0,begin=1, end = 1;
while(end <= mid){
count += end++;
while(count>sum){
count -= begin++;
}
if(count==sum){
ArrayList<Integer> list = new ArrayList();
for(int i=begin;i<end;i++){
list.add(i);
}
ret.add(list);
}
}
return ret;
}
}
发表于 2022-02-23 10:51:39
回复(0)
import java.util.ArrayList;
public class Solution {
public ArrayList<ArrayList<Integer>> FindContinuousSequence(int sum) {
ArrayList<ArrayList<Integer>> res = new ArrayList<>();
if(sum == 0){
return res;
}
//分别用left和right标记连续序列的前两个数
int left = 1;
int right = 2;
while(left < right){
//连续序列求和公式，属于闭区间
int total = (left + right) * (right - left + 1) / 2;
if(total == sum){
ArrayList<Integer> list = new ArrayList<>();
for(int i = left;i <= right;i++){
list.add(i);
}
res.add(list);
//从保存序列的下一位left重新开始遍历
left++;
}else if(total < sum){
//说明该序列区间中的数据和小于sum，应该扩大区间,以包含更多数据
right++;
}else{
//说明该序列区间中的数据和大于sum，应该缩小区间,以包含较少数据
left++;
}
}
return res;
}
}
发表于 2022-02-13 20:49:29
回复(0)
import java.util.ArrayList;
public class Solution {
public ArrayList<ArrayList<Integer> > FindContinuousSequence(int sum) {
// 滑动窗口解法：
// 定义返回
ArrayList<ArrayList<Integer>> ret = new ArrayList<ArrayList<Integer>>();
// 定义左边界和有边界
int left=1;
int right=1;
int windowSum=0;
// 开始滑动窗口，因为数列不可能全部分布在右半侧，所以当左边界超过sum/2就可以退出了
while(left <= sum/2){
// 窗口和小于目标值：窗口和吸收右边界，右边界+1
if(windowSum<sum){
windowSum+=right;
right++;
}
// 窗口和大于目标值：窗口和吐出左边界，左边界+1
else if(windowSum>sum){
windowSum-=left;
left++;
}
// 刚好等于：记录从左边界到右边界的数列，调整任意边界
else{
// 记录从左边界到右边界的数列
ArrayList<Integer> arr = new ArrayList<>();
for(int i=left;i<right;i++){
arr.add(i);
}
ret.add(arr);
// 窗口和吸收右边界，右边界+1（或者窗口和吐出左边界,左边界+1，只要打破窗口平衡即可）
windowSum+=right;
right++;
}
}
return ret;
}
}
发表于 2022-02-01 18:52:16
回复(0)
import java.util.*;
public class Solution {
public ArrayList<ArrayList<Integer> > FindContinuousSequence(int sum) {
//至少位两个以上的序列
//搜索序列为 1...sum/2+1;
// int[] seach = new int[sum / 2 + 1];
// for (int i = 0; i < seach.length; i++) {
// seach[i] = i+1;
// }
ArrayList<ArrayList<Integer>> list = new ArrayList<>();
//seach即1.2.3.4 ..... sum/2+1;
int n = 0;//基础项数最少为2；
while(n*n + n < 2*sum){
n++;
}
//此时n是最多的项数
for (int i = 2; i <= n; i++) {
//i是项数
ArrayList<Integer> sublist = new ArrayList<>();
// for (int j = 0; j < seach.length; j++) {
// int value = 0;
// for (int k = 0; k < i&& j+i<seach.length; k++) {
// value+=seach[k+j]
// }
// }
if((2*sum-i*i+i)%(2*i) != 0){
continue;
}
else{
int x = (2*sum-i*i+i)/(2*i);
for (int j = 0; j < i; j++) {
sublist.add(x+j);
}
}
list.add(sublist);
}
list.sort((a,b)->{
return b.size()-a.size();
});
return list;
}
}
发表于 2021-10-31 15:17:24
回复(0)
问题信息
难度：
206条回答
2053收藏
134835浏览
通过挑战的用户
查看代码-
2023-02-25 23:08:42 -
2023-02-01 13:32:49
-
2022-10-28 15:47:54
-
2022-09-17 11:34:54
-
2022-09-16 16:08:43
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
import java.util.ArrayList; public class Solution { public ArrayList<ArrayList<Integer> > FindContinuousSequence(int sum) { //存放结果 ArrayList<ArrayList<Integer> > result = new ArrayList<>(); //两个起点，相当于动态窗口的两边，根据其窗口内的值的和来确定窗口的位置和大小 int plow = 1,phigh = 2; while(phigh > plow){ //由于是连续的，差为1的一个序列，那么求和公式是(a0+an)*n/2 int cur = (phigh + plow) * (phigh - plow + 1) / 2; //相等，那么就将窗口范围的所有数添加进结果集 if(cur == sum){ ArrayList<Integer> list = new ArrayList<>(); for(int i=plow;i<=phigh;i++){ list.add(i); } result.add(list); plow++; //如果当前窗口内的值之和小于sum，那么右边窗口右移一下 }else if(cur < sum){ phigh++; }else{ //如果当前窗口内的值之和大于sum，那么左边窗口右移一下 plow++; } } return result; } }