57Ⅱ.和为s的连续正数序列

raylan.chen大约 2 分钟

尝试使用双指针（滑动窗口）来解决，

i 指向窗口左边界，j 指向窗口右边界，

当「i ~ j」的和小于 target，j++，sum += j

当「i ~ j」的和大于 target，sum -= i，i++，循环操作，直至 sum < target

当「i ~ j」的和等于 target，记录「i ~ j」的组合（为了避免再写个循环遍历「i ~ j」，滑动窗口移动过程中，采用 LinkedList 来存储「i ~ j」的临时组合），随后 sum -= i，i++，继续寻找下一个组合

// 代码存在冗余
class Solution {
    public int[][] fileCombination(int target) {
        // 使用 List 来装 「i ~ j」之间的数
        LinkedList<Integer> list = new LinkedList<>();
        List<int[]> res = new ArrayList<>();
        int i = 1;
        int j = 0;
        int sum = 0;
        while (i < target && j < target) {
            j++;
            sum += j;
            list.add(j);
            while (sum > target) {
                list.pollFirst();
                sum -= i++;
            }
            // 至少由两个数组成 target
            if (sum == target && i != j) {
                res.add(list.stream().mapToInt(Integer::intValue).toArray());
                list.pollFirst();
                sum -= i++;
            }
        }
        return res.stream().toArray(int[][]::new);
    }
}

//可以去除 i
class Solution {
    public int[][] fileCombination(int target) {
        LinkedList<Integer> list = new LinkedList<>();
        List<int[]> res = new ArrayList<>();
        int j = 0;
        int sum = 0;
        while (j < target - 1) {
            j++;
            sum += j;
            list.add(j);
            while (sum > target) {
                sum -= list.pollFirst();
            }
            if (sum == target) {
                res.add(list.stream().mapToInt(Integer::intValue).toArray());
                sum -= list.pollFirst();
            }
        }
        return res.stream().toArray(int[][]::new);
    }
}

优秀题解

class Solution {
    public int[][] fileCombination(int target) {
        int i = 1, j = 2, s = 3;
        List<int[]> res = new ArrayList<>();
        while(i < j) {
            if(s == target) {
                int[] ans = new int[j - i + 1];
                for(int k = i; k <= j; k++)
                    ans[k - i] = k;
                res.add(ans);
            }
            if(s >= target) {
                s -= i;
                i++;
            } else {
                j++;
                s += j;
            }
        }
        return res.toArray(new int[0][]);
    }
}

作者：Krahets
链接：https://leetcode.cn/problems/he-wei-sde-lian-xu-zheng-shu-xu-lie-lcof/solutions/574804/jian-zhi-offer-57-ii-he-wei-s-de-lian-xu-t85z/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

个人理解：

while(i < j) {

j 无需遍历到 target，

当 i 追上 j 时，证明（j - 1）+ j > target，j 往下遍历时（j - 1）+ j 的值会更大

57Ⅱ.和为s的连续正数序列

57Ⅱ.和为s的连续正数序列

参考链接

个人尝试

优秀题解