JZ41 和为S的连续正数序列

2021年9月14日23:04:13
数学方法


双指针

import java.util.ArrayList;
public class Solution {
    public ArrayList<ArrayList<Integer> > FindContinuousSequence(int sum) {
        ArrayList<ArrayList<Integer>> res = new ArrayList<>();
        int i= 1, j=2, s = 3;
        while(i<j){
            if(s == sum){
                ArrayList<Integer> temp = new ArrayList<>();
                for(int k = i; k<=j;k++) temp.add(k);
                res.add(temp);
            }
            if(s>=sum){
                //这里注意顺序 需要先-i 再 i++
                s-=i;
                i++;
            }
            else{
                j++;
                s+=j;
            }
        }
        return res;
    }
}

穷举

import java.util.ArrayList;
public class Solution {
    public ArrayList<ArrayList<Integer> > FindContinuousSequence(int sum) {
        ArrayList<ArrayList<Integer>> res = new ArrayList<>();
        for(int i =1; i<= sum/2 ; i++){
            int add = 0;
            int j =i;
            ArrayList<Integer> temp = new ArrayList<>();;
            while(add<sum) {
                add = add + j;
                temp.add(j++);
            }
            if(sum == add) res.add(temp);
        }
        return res;
    }
}