题目地址
https://leetcode-cn.com/problems/he-wei-sde-lian-xu-zheng-shu-xu-lie-lcof/
题目描述
输入一个正整数 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
思路
- 暴力解法，从1开始，往后递增，看和是否可以等于目标值，如果可以就记录这个序列。
一个优化的点是如果和已经大于目标值就没必要往后递增了。和j <= target/2 + 1作用类似，提前结束循环。
题解
/**
* @Author: vividzcs
* @Date: 2021/2/10 10:03 下午
*/
public class FindContinuousSequence {
public static void main(String[] args) {
int target = 9;
int[][] result = findContinuousSequence(target);
result = findContinuousSequenceV2(target);
for (int i=0; i<result.length; i++) {
for (int j=0; j<result[i].length; j++) {
System.out.print(result[i][j] + " ");
}
System.out.println();
}
}
private static int[][] findContinuousSequenceV2(int target) {
List<int[]> result = new ArrayList<>();
if (target <= 1) {
int[] arr = new int[1];
arr[0] = target;
result.add(arr);
return convertToArrayV2(result);
}
for (int i=1; i< target; i++) {
int sum = 0;
for (int j=i; j<target; j++) {
sum += j;
if (sum == target) {
int[] arr = new int[j - i + 1];
for (int index=0,value=i; value<=j; index++,value++) {
arr[index] = value;
}
result.add(arr);
break;
}
if (sum > target) {
break;
}
}
}
return convertToArrayV2(result);
}
private static int[][] convertToArrayV2(List<int[]> result) {
int[][] arr = new int[result.size()][];
for (int i=0; i<result.size(); i++) {
arr[i] = result.get(i);
}
return arr;
}
private static int[][] findContinuousSequence(int target) {
List<List<Integer>> result = new ArrayList<>();
if (target <= 1) {
List<Integer> list = new ArrayList<>();
list.add(target);
result.add(list);
return convertToArray(result);
}
for (int i=1; i< target; i++) {
int sum = 0;
List<Integer> list = new ArrayList<>();
for (int j=i; j<target; j++) {
sum += j;
list.add(j);
if (sum == target) {
result.add(list);
break;
}
if (sum > target) {
break;
}
}
}
return convertToArray(result);
}
private static int[][] convertToArray(List<List<Integer>> result) {
int[][] arr = new int[result.size()][];
for (int i=0; i<result.size(); i++) {
arr[i] = new int[result.get(i).size()];
for (int j=0; j<result.get(i).size(); j++) {
arr[i][j] = result.get(i).get(j);
}
}
return arr;
}
}
