package point;

import java.util.ArrayList;

/**
 * 题目: 和为 S 的连续正数序列
 * 输出所有和为 S 的连续正数序列。例如和为 100 的连续序列有:
 * [9, 10, 11, 12, 13, 14, 15, 16]
 * [18, 19, 20, 21, 22]
 *
 * @Author Gavin
 * @date 2022年08月06日 16:45
 */
public class sum_3 {
 public ArrayList<ArrayList<Integer>> solution(int sum) {
 ArrayList<ArrayList<Integer>> ret = new ArrayList<>();
 int start = 1, end = 2;
 int curSum = 3;
 /**
 * 临界值:
 * 只要end的值小于sum就行
 */
 while (end < sum) {
 //因为是连续序列(递增的特点),如果curSum>sum说明连续子序列加起来的总和就大于sum了,这时候左指针需要向右移动一位
 if (curSum > sum) {
 curSum -= start;
 start++;
 } else if (curSum < sum) {//和上面情况相反,子序列总和小于的话右指针就需要右移动一位
 end++;
 curSum += end;
 } else {
 ArrayList<Integer> list = new ArrayList<>();
 for (int i = start; i <= end; i++)
 list.add(i);
 ret.add(list);
 curSum -= start;
 start++;//左指针右移动一位
 end++;//右指针也右移动一位
 curSum += end;
 }
 }
 return ret;
 }

 /**
 *这种方式性能不是很好,但是容易理解
 */
 public static ArrayList<ArrayList<Integer>> solution_2(int sum) {
 ArrayList<ArrayList<Integer>> result = new ArrayList<>();
 if (sum <= 1) {
 ArrayList<Integer> pre = new ArrayList<>();
 pre.add(sum);
 result.add(pre);
 return result;
 }
 for (int i = 1; i < sum - 1; i++) {
 int preSum = i;
 ArrayList<Integer> pre = new ArrayList<>();
 pre.add(i);
 for (int j = i + 1; j < sum - 1; j++) {
 pre.add(j);
 preSum = preSum + j;
 if (preSum == sum) {
 result.add(pre);
 break;
 }else if(preSum>sum){
 break;
 }
 }
 }
 return result;
 }
}