思路:
1. 数学方法(求和公式)
设首项为x,项数为n,则末项为x+n-1,可得(2*x+n-1)*n=2*target
变形为x = (2*target-n*(n+1))/(2*n)
由求和易知,n < target /2
由题干正整数要求知,(n*(n+1))/2 < target, 2*target-n*(n+1)能整除 2*n
class Solution { public int[][] findContinuousSequence(int target) { int n = 2; int limit = target/2; LinkedList<int []> res = new LinkedList<>(); while (true) { int p1 = 2 * target - n * n + n; int p2 = n + n; if (p1 % p2 != 0) { n++; continue; } int i = p1 / p2; if (n >= limit || i <= 0) { break; } int[] arr = new int[n]; for (int k = i; k < i+n; k++) { arr[k-i] = k; } res.addFirst(arr); n++; } return res.toArray(new int[res.size()][]); } }
2. 滑动窗口(比数学方法通用)
设窗口的左边界为 i,右边界为 j,窗口大小为 sum。i,j一开始均在序列最左侧,sum=0。
窗口的左右边界都只能向右运动,能找全所有满足题意的序列(能依序找到1开头,2开头……的满足题意序列)。
当 sum < target 时,右边界 j 向右运动,即 sum += j++(sum+=j;j++;);
当 sum > target 时,左边界 i 向右运动,即 sum -= i++;
当 sum = target 时,记录结果,左边界 i 向右运动。
class Solution { public int[][] findContinuousSequence(int target) { int i = 1; // 滑动窗口的左边界 int j = 1; // 滑动窗口的右边界 int sum = 0; // 滑动窗口中数字的和 List<int[]> res = new ArrayList<>(); while (i <= target / 2) { if (sum < target) { // 右边界向右移动 sum += j++; }else if (sum > target) { // 左边界向右移动 sum -= i++; }else { // 记录结果 int[] arr = new int[j-i]; for (int k = i; k < j; k++) { arr[k-i] = k; } res.add(arr); // 左边界向右移动 sum -= i; i++; } } return res.toArray(new int[res.size()][]); } }