Topic 1

Input an increasing sort array and a number S, find two numbers in the array, make their sum S, and output any pair.

Seeing this problem, the simplest way we can think of is to fix a number first, and then judge whether the sum of n - 1 numbers is S, but the time complexity is O(n^2).
You can use the following method to solve it.

Next, let's look at the solution:
First, define two subscript indexes,
*The first points to the first of the array,
*The second points to the last of the array,
*If the sum is greater than the given value, the pointer to the last number moves forward;
*If the sum is less than the given value, the pointer to the first number moves backward;
*If there is such a pair of numbers, save and return true,
*Otherwise, return false
Code example:

public boolean findTwoNumbersSumIsValue(int[] array, int sum, int[] num1, int[] num2) {
        if (array == null || array.length <= 0) {
            return false;
        }
        boolean result = false;
        int start = 0;
        int end = array.length - 1;

        while (start < end) {
            if (array[start] + array[end] < sum) {
                start++;
            } else if(array[start] + array[end] > sum) {
                end--;
            } else {
                num1[0] = array[start];
                num2[0] = array[end];
                result = true;
                break;
            }
        }
        return result;
}

summary

Because the array is sorted, the larger number is always behind the smaller number, so here we use while (start < end) to judge. Scan the code array from both ends to the middle, so the time complexity is O(n)

Topic 2

Enter an integer S and print out all consecutive integer sequences with sum S, including at least two numbers

Train of thought I

Exhaustive law
*Accumulate from 1, and add to the list if the sum is S,
*Because the sequence is a continuous sequence with a difference of 1, so
*Exit cycle when accumulated (S / 2 + 1)

Code example:

public ArrayList<ArrayList<Integer>> FindContinuousSequence(int sum) {
        if (sum <= 0) {
            return null;
        }
        ArrayList<ArrayList<Integer>> result = new ArrayList<>();
        ArrayList<Integer> sequence;
        //Since the search sequence is at least 2 numbers, only sum / 2 + 1 can be found
        for (int i = 1; i < (sum / 2 + 1); i++) {
            int res = 0;
            int j = i;
            //Initialize sequence queue
            sequence = new ArrayList<>();
            //If the sequence sum is less than the given value
            while (res < sum) {
                res += j;
                sequence.add(j);
                j++;
            }
            //If the sequence sum is equal to the given value
            if (res == sum) {
                //Add sequence list to result list
                result.add(sequence);
            } else {
                //Sequence void and find again
                sequence.clear();
            }
        }

        return result;
}

summary

The time complexity of using this method is relatively large. Each time when the sequence is summed, if the condition is satisfied, it will be added directly to the list. If the condition is not satisfied, the sequence will be voided. It is necessary to start the calculation again from the next position of the previous time (for example, the first time starts to calculate the sequence sum from 1, and the second time continues to return to recalculate from 2). This is a waste of time. You can use the following method to continue the calculation based on the previous sequence sum without going back to recalculate.

Train of thought II

In fact, this problem can be done according to the idea of the above problem.
Two numbers, left and right, are used to represent the minimum and maximum values of the sequence,
*The initial value makes left = 1; right = 2;
*If the sum of the sequence left to right is greater than S, remove the minimum value (left + +),
*Otherwise, increase the maximum value (right + +),
*If equal, add the sequence to the list
Code example:

public ArrayList<ArrayList<Integer>> FindContinuousSequence1(int sum) {
        if (sum <= 0) {
            return null;
        }
        //List for storing sequences
        ArrayList<ArrayList<Integer>> result = new ArrayList<>();
        //minimum value
        int left = 1;
        //Maximum
        int right = 2;

        while (left < right) {
            //Sum of equal difference quantity S = (a1 + an) * n / 2;
            int res = (left + right) * (right - left + 1) / 2;
            //Sequence sum equal to given value
            if (res == sum) {
                ArrayList<Integer> sequence = new ArrayList<>();
                //Add the sequence to the sequence queue
                for (int i = left; i <= right; i++) {
                    sequence.add(i);
                }
                result.add(sequence);
                //Decrease minimum (move sequence right)
                left++;
            //Sequence sum greater than given
            } else if (res > sum) {
                //Remove minimum
                left++;
            //Sequence sum less than given
            } else {
                //Increase maximum
                right++;
            }
        }
        return result;
    }

summary

Generally, the sum of a sequence is calculated by loop, but considering that the sequence after each operation is mostly the same as the sequence before operation, only a number is increased or decreased, so the sum of the sequence after operation can be calculated on the basis of the sum of the previous sequence. In this way, unnecessary calculation can be reduced.