剑指 Offer 57 - II. 和为s的连续正数序列

剑指 Offer 57 - II. 和为s的连续正数序列

 

思路:

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()][]);
    }
}
上一篇:剑指 Offer 57 - II. 和为s的连续正数序列


下一篇:记一次nginx 403 错误排错