【剑指offer】-和为S的连续正数序列-39/67

电玩女神 2023-02-23 07:56 17阅读 0赞

# 1. 题目描述 #

小明很喜欢数学,有一天他在做数学作业时,要求计算出9~16的和,他马上就写出了正确答案是100。但是他并不满足于此,他在想究竟有多少种连续的正数序列的和为100(至少包括两个数)。没多久,他就得到另一组连续正数和为100的序列:18,19,20,21,22。现在把问题交给你,你能不能也很快的找出所有和为S的连续正数序列? Good Luck!

# 2. 题目分析 #

1.  给你一个数字sum，让你在0~sum之间求连续数字加起来等于sum的序列
2.  首先，比较好想的是O(n\*n)的做法，外层从1到sum，内层从2到sum，判断其是否等于sum，
3.  这里主要介绍第二种做法，类似[【剑指offer】-和为S的两个数-38/67][offer_-_S_-38_67]
4.  我们还是用两个指针，不过和上面不一样的是，我们第一个指针指向的是1(left)，第二个指针指向的是2(right)，我们用sum1来代表区间和
5.  如果sum1==sum的话，我们直接返回left~right，
6.  如果sum1 > sum的话，也就是我们目前的数字过大，我们需要将第一个指针往后一位(left++)，顺便更新sum1的值(sum1 = sum1 - left + 1)
7.  如果sum1 < sum的话，也就是我们目前的数字过小，我们需要将第二个指针往后一位(right++)，顺便更新sum1的值(sum1 = sum1 + right)

# 3. 题目代码 #

public static ArrayList<ArrayList<Integer>> FindContinuousSequence(int sum) {
        
    		ArrayList<ArrayList<Integer>> list = new ArrayList<>();
    		if (sum < 3) {
        
    			return list;
    		}
    		int left = 1;
    		int right = 2;
    		int sum1 = 3;
    		int mid = (sum / 2) + 1;
    		while (left < right && right <= mid) {
        
    			if (sum1 == sum) {
        
    				ArrayList<Integer> list2 = new ArrayList<>();
    				for (int i = left; i <= right; i++) {
        
    					list2.add(i);
    				}
    				list.add(list2);
    				right++;
    				sum1 = sum1 + right;
    			} else if (sum1 < sum) {
        
    				right++;
    				sum1 = sum1 + right;
    			} else {
        
    				sum1 = sum1 - left;
    				left++;
    			}
    		}
    		return list;
    	}

[offer_-_S_-38_67]: https://blog.csdn.net/qq_40915439/article/details/107148547