剑指 Offer 57 - II. 和为s的连续正数序列
题目描述
方法一：暴力枚举
package com.walegarrett.offer;
/**
* @Author WaleGarrett
* @Date 2021/2/12 16:42
*/
/**
* 题目描述：输入一个正整数 target ，输出所有和为 target 的连续正整数序列（至少含有两个数）。
* 序列内的数字由小到大排列，不同序列按照首个数字从小到大排列。
*/
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
/**
* 方法一：暴力枚举
*/
public class Offer_57_2 {
public int[][] findContinuousSequence(int target) {
List<int[]> list = new ArrayList<>();
int sum = 0, upp = (target - 1) / 2;
for(int i=1; i<= upp; i++){
for(int j=i;;j++){
sum+=j;
if(sum > target) {
sum = 0;
break;
}
else if(sum == target){
int[] ans = new int[j-i+1];
for(int k=i;k<=j;k++){
ans[k-i] = k;
}
list.add(ans);
sum = 0;
break;
}
}
}
return list.toArray(new int[list.size()][]);
}
}
方法二：枚举+数学优化
/**
* 方法二：枚举+递增序列的求和公式
*/
class Offer_57_2_2 {
public int[][] findContinuousSequence(int target) {
List<int[]> list = new ArrayList<>();
int sum = 0, upp = (target - 1) / 2;
for(int x=1; x<= upp; x++){
long delta = 1 - 4 * (x - (long) x * x - 2 * target);
if(delta<0)//无解
continue;
int delta_sqrt = (int)Math.sqrt(delta + 0.5);
if((long)delta_sqrt * delta_sqrt == delta && (delta_sqrt-1)%2 == 0){
int y = (-1 + delta_sqrt) / 2;
if(x<y){
int[] ans = new int[y-x+1];
for(int k=x;k<=y;k++){
ans[k-x]=k;
}
list.add(ans);
}
}
}
return list.toArray(new int[list.size()][]);
}
}
方法三：双指针法
/**
* 方法三：双指针法
*/
class Offer_57_2_3 {
public int[][] findContinuousSequence(int target) {
List<int[]> list = new ArrayList<>();
for(int l=1,r=2;l<r;){
int sum = (l+r) *(r-l+1) /2;
if(sum == target){
int[] ans = new int[r-l+1];
for(int k=l;k<=r;k++)
ans[k-l] = k;
list.add(ans);
l++;
}else if(sum<target)
r++;
else if(sum>target)
l++;
}
return list.toArray(new int[list.size()][]);
}
}
