面试题57 - II. 和为s的连续正数序列(一般)

输入一个正整数 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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/he-wei-sde-lian-xu-zheng-shu-xu-lie-lcof

思路1：

  • 创建双指针i，j都指向1，sum求和。i，j之间就是窗口大小

  • 若target大于sum说明数字之和 不够，右指针j需要右移j++直至sum小于target（等于时直接跳出存储结果到list）

  • 若此时target小于sum说明数字之和 超出，调整左指针i–直至满足sum=target

算法步骤

  • 创建指针、求和变量和list集合（用于存储满足的结果）
  • 当左指针i小于等于target/2时，判断sum和target的大小关系，sum小则右指针往右移动一位，大则左移一位
  • 等于时记录到list集合中，并且让sum减去i，左指针右移，重新下一次寻找
  • list转换为int[][]类型后返回
  • 注意：题目的条件是至少返回两个连续正整数，所以判断循环条件为i <= target/2。假设i > target/2，那么下一位i + 1与i的和必定大于target。“=” 的情况之一例如9，target/2 = 4，存在i+i+1=target，因此列入其中。

时间复杂度：O(target) 指针只向右移动，遍历一遍为target/2次
空间复杂度：O(1) 除了list和目标数组都是常量

作者：Chamlin
链接：https://leetcode-cn.com/problems/he-wei-sde-lian-xu-zheng-shu-xu-lie-lcof/solution/he-wei-sde-lian-xu-zheng-zheng-shu-xu-lie-javati-j/

注意

java中动态二维数组转换为二维数组，这里也不是很明白为什么用new int [ 0 ] []，也可以用new int [ alist.size() ] [],应该就是初始化

具体探究，请深入理解List的toArray()方法和toArray(T[] a)方法

代码1：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
    public int[][] findContinuousSequence(int target) {
        int i=1,j=1,sum=0;
        //怎么返回int[][]
        ArrayList<int[]> alist = new ArrayList<>();
        while(i<=target/2)// target/2+(target+1)/2 大于target 两个数就会大于target 就不用数了
        {
            if(sum<target)//比目标小，右向右边移动
                sum+=j++;
            else if(sum>target)//比目标大，左向右移动
                sum-=i++;
            else//找到，放到数组里面,大小就是j-i个窗口
            {
                int[] res = new int[j-i];//用来存放目标数组
                for(int k=i;k<j;k++){
                    res[k-i]=k;
                }
                alist.add(res);
                //左开始移动
                sum-=i++;
            }
        }
        return alist.toArray(new int[0][]);
    }
}