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

2022-01-15  本文已影响0人  itbird01
题目.png

题意:输入一个正整数 target ,输出所有和为 target 的连续正整数序列(至少含有两个数)。
序列内的数字由小到大排列,不同序列按照首个数字从小到大排列。

解题思路

解法1:
1.和为target,所以值最大不会超过target / 2 + 1
2.输出结果需要二维数组,但是由给出的例子分析,每个结果数组可能长度不唯一,所以暂时先以list存储结果数据
3.从1开始遍历,到target / 2 + 1,如果遇到sum==target,则将结果保存,保存之后,回退遍历指针为上一次+1

解题遇到的问题

后续需要总结学习的知识点

##解法1
import java.util.ArrayList;
import java.util.List;

class Solution {
    public int[][] findContinuousSequence(int target) {
        int k = target / 2 + 1;
        int sum = 0;
        List<List<Integer>> list = new ArrayList<List<Integer>>();
        for (int i = 1; i <= k; i++) {
            sum = 0;
            for (int l = i; sum <= target; l++) {
                sum += l;
                if (sum == target) {
                    List<Integer> temp = new ArrayList<Integer>();
                    for (int l2 = i; l2 <= l; l2++) {
                        temp.add(l2);
                    }
                    list.add(temp);
                    break;
                }
            }
        }
        int[][] ans = new int[list.size()][];
        for (int i = 0; i < ans.length; i++) {
            int[] m = new int[list.get(i).size()];
            for (int l = 0; l < list.get(i).size(); l++) {
                m[l] = list.get(i).get(l);
            }
            ans[i] = m;
        }
        return ans;
    }
}
上一篇下一篇

猜你喜欢

热点阅读