剑指offer-题41:和为s的两个数字VS和为s的连续正数序列

题目描述

题一:输入一个递增排序的数组和一个数字S,在数组中查找两个数,使得他们的和正好是S,如果有多对数字的和等于S,输出两个数的乘积最小的。

题二:输入一个正数s,打印出所有和为s的连续正数序列(至少含有2个数),例如输入15,由于1+2+3+4+5=4+5+6=7+8=15。所以结果打印出3个连续序列1 ~ 5,4 ~ 6,7 ~ 8

实验平台:牛客网


解决思路:

题一的解题思路:

这里写图片描述
这里写图片描述
由于题目要求在有多对数字的和等于S的情况下,需要输出两个数的乘积最小的。所以,我们需要遍历整个数组,当两个数字的和等于S时,用两个变量分别存储此时两个数字的值,从而在之后的遍历中,如果又有新的两个数字的和等于S,将它们的积与之前存储的两个变量的积相比较,取积小的两个数即可。

题二的解题思路:
这里写图片描述
这里写图片描述

题一

java:

import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> FindNumbersWithSum(int [] array,int sum) {
        ArrayList<Integer> twoNum = new ArrayList<Integer>();
        if (array.length == 0) {
            return twoNum;
        } else {
            int smallIndex = 0;
            int bigIndex = array.length - 1;
            int smallNum = 0;
            int bigNum = 0;
            int multyplyResult = array[bigIndex] * array[bigIndex - 1];

            while (smallIndex < bigIndex) {
                if (array[smallIndex] + array[bigIndex] == sum && array[smallIndex] * array[bigIndex] <= multyplyResult) {
                    smallNum = array[smallIndex];
                    bigNum = array[bigIndex];
                    multyplyResult = smallNum * bigNum;
                    bigIndex--;
                } else if (array[smallIndex] + array[bigIndex] > sum) {
                    bigIndex--;
                } else {
                    smallIndex++;
                }
            }
            if(smallNum + bigNum == sum){
                twoNum.add(new Integer(smallNum));
                twoNum.add(new Integer(bigNum));
            }
            return twoNum;
        }
    }
}

题二

java:

import java.util.ArrayList;
public class Solution {
    public ArrayList<ArrayList<Integer> > FindContinuousSequence(int sum) {
       ArrayList<ArrayList<Integer>> list = new ArrayList<ArrayList<Integer>>();
        if (sum < 2) {
            return list;
        } else {
            int small = 1;
            int big = 2;
            int middle = (sum + 1) / 2;
            int curSum = small + big;
            while (small < middle) {
                if (curSum == sum) {
                    list.add(getList(small, big));
                }
                while (curSum > sum && small < middle) {
                    curSum -= small;
                    small++;
                    if (curSum == sum) {
                        list.add(getList(small, big));
                    }
                }
                big++;
                curSum += big;
            }
            return list;
        }
    }

    public ArrayList<Integer> getList(int small, int big) {
        ArrayList<Integer> arrayList = new ArrayList<Integer>();
        for (int i = small; i <= big; i++) {
            arrayList.add(new Integer(i));
        }
        return arrayList;
    }
}
版权声明:本文为wang454592297原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/wang454592297/article/details/79929852

智能推荐

1264页面推荐(中等 union all )稍微的难点在于找1的朋友

![在这里插入图片描述](https://img-blog.csdnimg.cn/20200904233840843.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NTMxNTk0,size_16,color_FFFFFF,t...

单链表+单链表代码(链表最基础)

链表 链表是有顺序的表,在内存中存储: 链表是以节点的方式存储的 每个节点包括data域,next域:指向下一个节点 如图:发现链表的各个节点不一定是连续存放的,有跳跃的,不是连续存储 链表分为带头节点的链表和没有头结点的链表 添加: 1.先创建一个head头结点,作用就是单链表的头 2.后面每添加一个节点,就直接加入到链表最后 遍历: 代码 添加节点到链表里: 这里借助于temp节点,通过循环找...

Rtthread学习笔记(十三)RT-Thread Studio开启硬件看门狗Watchdog

一、开启硬件看门狗Watchdog 1、配置RT-Thread Settings 2、开启stm32f1xx_hal_conf.h中的宏定义 3.使用RT接口函数初始化硬件看门狗...

TYVJ 4864 天天去哪吃 || 清北学堂金秋杯大奖赛

题目描述: 记录一下i这个值上次出现的位置在哪里,就是pre...

java反编译

jvm 把Boolean类型的值flag当做int类型处理。​​​ Foo.java: 由 class 文件生成 jasm 文件:java -jar asmtools.jar jdis Foo.class > Foo.jasm  修改jasm文件: 执行反编译: java -jar jd-gui-1.6.6.jar File 打开Foo.class文件:b修改为2 重新执行java...

猜你喜欢

【学习笔记】03-v-html的学习和示例

v-html的认识和使用 示例: 显示结果: 注意:v-html是有复制的...

Java实现在线考试系统(系统介绍)

1.和现在有的考试系统有以下几种优势: a.和现在有的系统比较起来,本系统有科目、章节、老师、学生、班级等信息的管理,还有批阅试卷查看已批阅试卷等。传统的考试系统划分并不细,业务功能简单。 b.和学校的考试系统还有外面的考试系统比较起来,本系统是B/S结构,学校的考试系统一般为C/S结构,性能方面不如B/S结构,并且C/S接口需要安装客户端,客户端压力很大,我的系统只需要电脑具有浏览器,在同一局域...

计算机视觉--多视几何初步尝试

基础矩阵的原理 K和K’分别是两个相机的参数矩阵。p和p’是X在平面π的坐标表示。所以可以得出 具体计算过程 代码: #!/usr/bin/env python coding: utf-8 from PIL import Image from numpy import * from pylab import * import numpy as np from imp ...

java初学者怎么学习才可以快速入门

java初学者怎么学习才可以快速入门 一、了解JAVA 我们要知道:Java是由Sun Microsystems公司于1995年5月推出的Java面向对象程序设计语言。 Java之父:詹姆斯·高斯林 1.1 java的三个体系 Java SE(Java Platform Standard Edition)。Java SE 以前称为 J2SE。它允许开发和部署在桌面、服务器、嵌入式环境...

字段属性之主键&增删改查&自增长&唯一键约束

字段属性之主键&自增长&唯一键约束 主键 主键:primary key 主要的键 一张表中只有一个字段可以使用对应的键,用来唯一的约束该字段里面的数据,不能重复,这种称之为主键 一张表只能最多一个主键 增加主键 SQL操作中有多种方式增加主键大体分为三种 1.在创建表的时候直接在字段之后跟primary key关键字(主键本身不允许为空) 优点:非常直接:缺点:只能使用一个字段作为...