Sword finger 41 Continuous positive sequence with sum S

Title Description

Xiao Ming likes math very much. One day when he was doing his math homework, he asked to calculate the sum of 9 ~ 16. He immediately wrote the correct answer is 100. But he is not satisfied with this. He is wondering how many kinds of continuous positive number sequences have a sum of 100 (including at least two numbers). Before long, he got another set of sequences with a continuous positive sum of 100: 18, 19, 20, 21, 22. Now let'S leave the problem to you. Can you quickly find all the continuous positive sequences with sum S? Good Luck!
 

Output Description:

Output all continuous positive number sequences with sum S. The sequence is from small to large, and the sequence is from small to large
 

thinking

Idea 1: sliding window method (interval continuous, double pointers moving in the same direction). Two numbers small and big are used to represent the minimum and maximum values of the sequence respectively. First, initialize small to 1 and big to 2 If the sum of the sequence from small to big is greater than s, remove the smaller value from the sequence, that is, increase the value of small. If the sum of the sequence from small to big is less than s, you can increase the big to make the sequence contain more numbers. Because this sequence must have at least two numbers, we keep increasing small to (1+s) / 2.

 

Idea 2: you can also try mathematical analysis.

 

Solution 1

import java.util.ArrayList;
public class Solution {
    // Version 1
    public ArrayList<ArrayList<Integer> > FindContinuousSequence(int sum) {
        ArrayList<ArrayList<Integer> >  res = new ArrayList<>();
        int small = 1, big = 2;  //Two starting points, equivalent to both sides of the dynamic window
        while (small < big){ // small < (sum + 1) / 2  Can also pass
            int tempSum = (small + big)*(big - small + 1) / 2;
            if (tempSum == sum){
                ArrayList<Integer> list = new ArrayList<>(); // Every time I use it new One, so you don't need to run out list.clear()Yes
                for (int i = small; i <= big; i++) {
                    list.add(i);
                }
                res.add(list);
                big++;
            }else if (tempSum > sum){  //If the sum of the values in the current window is greater than sum,Then move the left window to the right
                small++;
            }else{  //If the sum of the values in the current window is less than sum,Then move the right window to the right
                big++;
            }
        }
        return res;
    }
    // Version 2
    // The difference from version 1 is that the sum of continuous sequences can be obtained, so the sum of sequences after operation can be obtained on the basis of the sum of the previous sequence.
    public ArrayList<ArrayList<Integer> > FindContinuousSequence(int sum) {
        ArrayList<ArrayList<Integer> >  res = new ArrayList<>();
        int small = 1, big = 2;  //Two starting points, equivalent to both sides of the dynamic window
        int tempSum = small + big;
        while (small < big){ // small < (sum + 1) / 2  Can also pass
            if (tempSum == sum){
                ArrayList<Integer> list = new ArrayList<>();
                for (int i = small; i <= big; i++) {
                    list.add(i);
                }
                res.add(list);
                big++;
                tempSum += big;
            }else if (tempSum > sum){  //If the sum of the values in the current window is greater than sum,Then move the left window to the right
                tempSum -= small;
                small++;
            }else{  //If the sum of the values in the current window is less than sum,Then move the right window to the right
                big++;
                tempSum += big;
            }
        }
        return res;
    }
}

 

Solution 2

M. if you want to do it later, you can try to solve it with the idea of mathematics.

 

Self written violence traversal method

import java.util.ArrayList;
public class Solution {
    // The idea is to calculate the sum formula according to the sequence of equal differences(count*(a1+an))/2,Traverse start position a1,Then traverse count,See if it meets the meaning of the question
    // Test case, input 15; Output 1~5 ,4~6 ,7~8
    public ArrayList<ArrayList<Integer> > FindContinuousSequence(int sum) {
        ArrayList<ArrayList<Integer> > res = new ArrayList<>();
        ArrayList<Integer> list = new ArrayList<>();
        for (int i = 1; i <= sum / 2 + 1; i++) {
            int num = i;
            int counts = sum / 2 + 1;
            while (counts >= 2){
                if (counts*(num+num+counts-1)/2 == sum){  // core
                    for (int j = num; j <=num+counts-1;j++)
                        list.add(j);
                    res.add(new ArrayList<>(list));
                    list.clear();
                    break;
                }
                counts--;
            }
        }
        return res;
    }
}

 

harvest

If you need to use ArrayList multiple times to add data, you can create a new one each time, so you don't have to share one and use up the list Clear ().

 

Posted by locomotive on Fri, 20 May 2022 11:24:53 +0300