剑指offer：和为s的连续正数序列

系统管理员 2022-09-01 10:56 147阅读 0赞

![转自leetcode剑指offer][leetcode_offer]  
leetcode官方挺多解法的，比较直观的是暴力解法，一开始不知道list里面能装数组int\[\]这样，浪费了很多时间在转换上面，下面是看了题解之后写的代码：

class Solution { 
        public int[][] findContinuousSequence(int target) { 
            if(target<3) return new int[0][0];
            int n=1;
            List<int[]> resList=new LinkedList<>();
            while(n<=target/2){ 
                int tot=0;
                for(int i=n;i<target;i++){ 
                    tot+=i;
                    if(tot>target)break;
                    if(tot==target){ 
                        int[] tempArr=new int[i-n+1];
                        for(int j=n;j<=i;j++){ 
                            tempArr[j-n]=j;
                        }
                        resList.add(tempArr);
                        break;
                    }
                }
                n++;
            }
            int[][] res=new int[resList.size()][];
            for(int i=0;i<resList.size();i++){ 
                res[i]=resList.get(i);
            }
            return res;
        }
    }

官方的比较简洁，也贴上：

class Solution { 
        public int[][] findContinuousSequence(int target) { 
            List<int[]> vec = new ArrayList<int[]>();
            int sum = 0, limit = (target - 1) / 2; // (target - 1) / 2 等效于 target / 2 下取整
            for (int i = 1; i <= limit; ++i) { 
                for (int j = i;; ++j) { 
                    sum += j;
                    if (sum > target) { 
                        sum = 0;
                        break;
                    } else if (sum == target) { 
                        int[] res = new int[j - i + 1];
                        for (int k = i; k <= j; ++k) { 
                            res[k - i] = k;
                        }
                        vec.add(res);
                        sum = 0;
                        break;
                    }
                }
            }
            return vec.toArray(new int[vec.size()][]);
        }
    }
    
    作者：LeetCode-Solution
    链接：https://leetcode-cn.com/problems/he-wei-sde-lian-xu-zheng-shu-xu-lie-lcof/solution/mian-shi-ti-57-ii-he-wei-sde-lian-xu-zheng-shu-x-2/
    来源：力扣（LeetCode）

[leetcode_offer]: /images/20220829/b40ed48ef8854be79de418e9b3931cd0.png