面试题41:和为s的两个数VS和为s的连续正数数列

2024-09-06 00:58

本文主要是介绍面试题41:和为s的两个数VS和为s的连续正数数列,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

问题说明:

1.和为s的两个数问题是从一个排序的数组中找出和为s的两个数;

2.原题是找出一个即可,现在全部找出;

3.和为s的连续正数数列是给定一个数找出所有连续正数数列的和为s,例如s为9,(2,3,4)就是其中一组。

(一)和为s的两个数问题

public static int findNumbersWithSum(int[] sorted, int fromIndex, int toIndex, int sum){if(null == sorted || sorted.length == 0){throw new IllegalArgumentException();}// allow one element in sorted but at least two elment to make a pairif(fromIndex > toIndex){throw new IndexOutOfBoundsException("fromIndex : " + fromIndex + "toIndex : " + toIndex);}int countPair = 0;// return value int smallIndex = fromIndex;int bigIndex = toIndex;int currentSum = 0;while(smallIndex < bigIndex){currentSum = sorted[smallIndex] + sorted[bigIndex];if(currentSum > sum){bigIndex--;}if(currentSum < sum){smallIndex++;}if(currentSum == sum){int firstNotEqualSmall = smallIndex + 1;while(firstNotEqualSmall < bigIndex && (sorted[firstNotEqualSmall] == sorted[smallIndex])){firstNotEqualSmall++;}int firstNotEqualBig = bigIndex - 1;while(firstNotEqualBig > smallIndex && (sorted[firstNotEqualBig] == sorted[bigIndex])){firstNotEqualBig--;}//int equalSmallLen = firstNotEqualSmall - smallIndex;//int equalBigLen = bigIndex - firstNotEqualBig;// may be i == j so add condition by i < jfor(int i = smallIndex; i < firstNotEqualSmall; i++){for(int j = bigIndex; (i < j) && (j > firstNotEqualBig); j--){countPair++;System.out.println("equal sum = " + sum + " pair index is (" + i + "," + j + ")" + " and value is (" + sorted[i] + "," + sorted[j] + ")");}}// go on to find againsmallIndex = firstNotEqualSmall;bigIndex = firstNotEqualBig;}// end if ==}//end whilereturn countPair;
}
(二)和为s的连续正数数列

public static void findContinousSequence(int sum){if(sum < 3){return ;}int small = 1;int big = 2;int currentSum = 3;int middle = (1 + sum) >> 1;while(small < middle){if(currentSum == sum){print(small, big);}while(currentSum > sum && small < middle){currentSum -= small;small++;if(currentSum == sum){print(small, big);}}// maybe currentSum < sum or small >= middlebig++;currentSum += big;}
}

这篇关于面试题41:和为s的两个数VS和为s的连续正数数列的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1140543

相关文章

C语言实现两个变量值交换的三种方式

《C语言实现两个变量值交换的三种方式》两个变量值的交换是编程中最常见的问题之一,以下将介绍三种变量的交换方式,其中第一种方式是最常用也是最实用的,后两种方式一般只在特殊限制下使用,需要的朋友可以参考下... 目录1.使用临时变量(推荐)2.相加和相减的方式(值较大时可能丢失数据)3.按位异或运算1.使用临时

java两个List的交集,并集方式

《java两个List的交集,并集方式》文章主要介绍了Java中两个List的交集和并集的处理方法,推荐使用Apache的CollectionUtils工具类,因为它简单且不会改变原有集合,同时,文章... 目录Java两个List的交集,并集方法一方法二方法三总结java两个List的交集,并集方法一

Python如何计算两个不同类型列表的相似度

《Python如何计算两个不同类型列表的相似度》在编程中,经常需要比较两个列表的相似度,尤其是当这两个列表包含不同类型的元素时,下面小编就来讲讲如何使用Python计算两个不同类型列表的相似度吧... 目录摘要引言数字类型相似度欧几里得距离曼哈顿距离字符串类型相似度Levenshtein距离Jaccard相

使用Navicat工具比对两个数据库所有表结构的差异案例详解

《使用Navicat工具比对两个数据库所有表结构的差异案例详解》:本文主要介绍如何使用Navicat工具对比两个数据库test_old和test_new,并生成相应的DDLSQL语句,以便将te... 目录概要案例一、如图两个数据库test_old和test_new进行比较:二、开始比较总结概要公司存在多

C#比较两个List集合内容是否相同的几种方法

《C#比较两个List集合内容是否相同的几种方法》本文详细介绍了在C#中比较两个List集合内容是否相同的方法,包括非自定义类和自定义类的元素比较,对于非自定义类,可以使用SequenceEqual、... 目录 一、非自定义类的元素比较1. 使用 SequenceEqual 方法(顺序和内容都相等)2.

锐捷和腾达哪个好? 两个品牌路由器对比分析

《锐捷和腾达哪个好?两个品牌路由器对比分析》在选择路由器时,Tenda和锐捷都是备受关注的品牌,各自有独特的产品特点和市场定位,选择哪个品牌的路由器更合适,实际上取决于你的具体需求和使用场景,我们从... 在选购路由器时,锐捷和腾达都是市场上备受关注的品牌,但它们的定位和特点却有所不同。锐捷更偏向企业级和专

poj2406(连续重复子串)

题意:判断串s是不是str^n,求str的最大长度。 解题思路:kmp可解,后缀数组的倍增算法超时。next[i]表示在第i位匹配失败后,自动跳转到next[i],所以1到next[n]这个串 等于 n-next[n]+1到n这个串。 代码如下; #include<iostream>#include<algorithm>#include<stdio.h>#include<math.

Android平台播放RTSP流的几种方案探究(VLC VS ExoPlayer VS SmartPlayer)

技术背景 好多开发者需要遴选Android平台RTSP直播播放器的时候,不知道如何选的好,本文针对常用的方案,做个大概的说明: 1. 使用VLC for Android VLC Media Player(VLC多媒体播放器),最初命名为VideoLAN客户端,是VideoLAN品牌产品,是VideoLAN计划的多媒体播放器。它支持众多音频与视频解码器及文件格式,并支持DVD影音光盘,VCD影

XTU 1233 n个硬币连续m个正面个数(dp)

题面: Coins Problem Description: Duoxida buys a bottle of MaiDong from a vending machine and the machine give her n coins back. She places them in a line randomly showing head face or tail face o

荣耀嵌入式面试题及参考答案

在项目中是否有使用过实时操作系统? 在我参与的项目中,有使用过实时操作系统。实时操作系统(RTOS)在对时间要求严格的应用场景中具有重要作用。我曾参与的一个工业自动化控制项目就采用了实时操作系统。在这个项目中,需要对多个传感器的数据进行实时采集和处理,并根据采集到的数据及时控制执行机构的动作。实时操作系统能够提供确定性的响应时间,确保关键任务在规定的时间内完成。 使用实时操作系统的