1. 题目描述
小明很喜欢数学,有一天他在做数学作业时,要求计算出9~16的和,他马上就写出了正确答案是100。但是他并不满足于此,他在想究竟有多少种连续的正数序列的和为100(至少包括两个数)。没多久,他就得到另一组连续正数和为100的序列:18,19,20,21,22。现在把问题交给你,你能不能也很快的找出所有和为S的连续正数序列? Good Luck!
2. 题目分析
- 给你一个数字sum，让你在0~sum之间求连续数字加起来等于sum的序列
- 首先，比较好想的是O(n*n)的做法，外层从1到sum，内层从2到sum，判断其是否等于sum，
- 这里主要介绍第二种做法，类似【剑指offer】-和为S的两个数-38/67
- 我们还是用两个指针，不过和上面不一样的是，我们第一个指针指向的是1(left)，第二个指针指向的是2(right)，我们用sum1来代表区间和
- 如果sum1==sum的话，我们直接返回left~right，
- 如果sum1 > sum的话，也就是我们目前的数字过大，我们需要将第一个指针往后一位(left++)，顺便更新sum1的值(sum1 = sum1 - left + 1)
- 如果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; }
