剑指Offer-和为S的连续正数序列

题目描述

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

输出描述: 输出所有和为S的连续正数序列。序列内按照从小至大的顺序,序列间按照开始数字从小到大的顺序

思路

思路一:

暴力,时间复杂度太高,肯定不合适。

思路二(滑动窗口):

  1. 用两个数字left和right分别表示序列的最小值和最大值,
  2. 首先将left初始化为1,right初始化为2,
  3. 如果从left到right的和大于sum,我们就从序列中去掉较小的值(即增大left), 相反,只需要增大right。
  4. 终止条件为:一直增加left到(1+sum)/2

注:等差数列中

\(S(n)=(a1+an)*n/2\)

\(n=an-a1+1\)

\(S(n)=(a1+an)*(an-a1+1)*n/2\)

代码实现

package Array;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * 和为S的连续正数序列
 * 小明很喜欢数学,有一天他在做数学作业时,要求计算出9~16的和,他马上就写出了正确答案是100。
 * 但是他并不满足于此,他在想究竟有多少种连续的正数序列的和为100(至少包括两个数)。
 * 没多久,他就得到另一组连续正数和为100的序列:18,19,20,21,22。
 * 现在把问题交给你,你能不能也很快的找出所有和为S的连续正数序列? Good Luck!
 * 输出描述:
 * 输出所有和为S的连续正数序列。序列内按照从小至大的顺序,序列间按照开始数字从小到大的顺序
 */
public class Solution40 {
    public static void main(String[] args) {
        Solution40 solution40 = new Solution40();

        ArrayList<ArrayList<Integer>> lists = solution40.FindContinuousSequence_2(100);
        for (ArrayList<Integer> list :
                lists) {
            System.out.println(list);
        }
    }

    /**
     * 等差数列Sn=(a1+an)*n/2   n=an-a1+1 Sn=(a1+an)*(an-a1+1)/2
     * 初始化left=1,big=2;
     * left到right序列和小于sum,right++;大于sum,left++;
     * 当left增加到(1+sum)/2是停止
     *
     * @param sum
     * @return
     */
    public ArrayList<ArrayList<Integer>> FindContinuousSequence_2(int sum) {
        ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
        if (sum < 3)
            return result;
        ArrayList<Integer> list;
        int left = 1;
        int right = 2;
        int total = 0;
        while (left < right && left < (1 + sum) / 2) {
            total = (left + right) * (right - left + 1) / 2;
            if (total == sum) {
                list = new ArrayList<Integer>();
                int temp = left;
                while (temp <= right) {
                    list.add(temp);
                    temp++;
                }
                result.add(list);
                left++;
                right++;
            } else if (total < sum) {
                right++;
            } else {
                left++;
            }
        }
        return result;
    }

    /**
     * 暴力
     *
     * @param sum
     * @return
     */
    public ArrayList<ArrayList<Integer>> FindContinuousSequence(int sum) {
        ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
        ArrayList<Integer> list = new ArrayList<Integer>();
        for (int i = 1; i <= sum / 2; i++) {
            list.add(i);
            for (int j = i + 1; j <= sum / 2 + 1; j++) {
                list.add(j);
                int total = 0;
                for (int x = 0; x < list.size(); x++) {
                    total += list.get(x);
                }
                if (total == sum) {
                    result.add(list);
                    list = new ArrayList<Integer>();
                    break;
                } else if (total > sum) {
                    list.clear();
                    break;
                }
            }
        }
        return result;
    }
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Coding迪斯尼

详解神经网络算法所需最基础数据结构Tensor及其相关操作

974
来自专栏北京马哥教育

Python神技能:六张表 搞定 Xpath 语法

1555
来自专栏小小挖掘机

如何使用tensorflow做张量排序和字符串拼接?

本文,将总结一下最近使用tensorflow中遇到的两个小需求:张量排序和字符串拼接,咱们一起来学习一下,嘻嘻!

2522
来自专栏java一日一条

java float double精度为什么会丢失?浅谈java的浮点数精度问题

由于对float或double 的使用不当,可能会出现精度丢失的问题。问题大概情况可以通过如下代码理解:

1271
来自专栏机器学习从入门到成神

2013百度校招笔试真题以及解析(二)

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/sinat_35512245/articl...

1031
来自专栏大数据学习笔记

面试算法题

题目来源于牛客网:https://www.nowcoder.com/ta/coding-interviews 1、二维数组中的查找 在一个二维数组中,每一行都按...

1.3K6
来自专栏数据结构与算法

洛谷T21776 子序列

题目描述 你有一个长度为 nn 的数列 ,这个数列由 0,10,1 组成,进行 mm 个的操作: 1~l~r1 l r :把数列区间 [l, r][l,r] ...

4158
来自专栏武培轩的专栏

剑指Offer-连续子数组的最大和

题目描述 在古老的一维模式识别中,常常需要计算连续子向量的最大和,当向量全为正数的时候,问题很好解决。但是,如果向量中包含负数,是否应该包含某个负数,并期望旁边...

2812
来自专栏机器学习和数学

[ Tensorflow]Tensorflow Reduction operations

reduce系列在平时工程中是经常使用的,其中reduce_sum是使用最频繁的一个。主要用在计算loss的时候,当我们定义好loss之后,我们一般要求loss...

3634
来自专栏机器学习算法工程师

最长公共子序列与最长公共子串

0. 引言 最近鄙人面试百度,出了这道求解公子序列长度的算法题。故此总结一下,这是一个很典型的题目,希望对大家将来的面试中能起到学习的作用。 1. 问题描述 子...

41211

扫码关注云+社区

领取腾讯云代金券