剑指offer----和为S的两个数----java实现

淩亂°似流年 2022-09-25 06:20 56阅读 0赞

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

分析要求：

（1）数组是递增的数组；即数据已经是有序的了。

（2）输出乘积最小的一对和为S的数；和相等的情况下，两个数相差越大，乘积越小。

思路：

定义两个指针，一个是指向数组的起始位置变量设为low，一个指向数组的终止位置处变量设为high。

1）如果和为S则停止查找。跳出当前循环

2）如果和小于S则low++，

3）如果和大于S则high--；

import java.util.ArrayList;
    
    public class Sum
    {
    public ArrayList<Integer> FindNumbersWithSum(int [] array,int sum) 
    {
    	 ArrayList<Integer> list = new ArrayList<Integer>();
            if(array.length == 0 ||array==null)
            {
            	return list;
            }
            int low = 0;//让一个引用变量指向数组的头
            int high = array.length - 1;//一个引用变量指向数组的尾
            while(low < high)
            {
            	int cursum = array[low]+array[high];
            	//当找到第一组和为S的数对就停止寻找，因为第一对的两个数之间相差最大，乘积最小
            	if(cursum == sum)
            	{
            		list.add(array[low]);
            		list.add(array[high]);
            		break;
            	}
            	else if(cursum < sum)
            	{
            		low++;
            	}
            	else
            	{
            		high--;
            	}
            }
            return list;
    }
    
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，56人围观）

还没有评论，来说两句吧...

相关阅读

相关【剑指offer】-和为S的两个数-38/67

1. 题目描述输入一个递增排序的数组和一个数字S，在数组中查找两个数，使得他们的和正好是S，如果有多对数字的和等于S，输出两个数的乘积最小的。 2. 题目分析

淩亂°似流年/ 2023年02月23日 07:55/ 0 赞/ 67 阅读

相关剑指offer----和为S的两个数----java实现

输入一个递增排序的数组和一个数字S，在数组中查找两个数，使得他们的和正好是S，如果有多对数字的和等于S，输出两个数的乘积最小的。分析要求：（1）数组是递增的数组；即数

淩亂°似流年/ 2022年09月25日 06:20/ 0 赞/ 57 阅读

相关剑指·offer：和为S的两个数字

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

Bertha 。/ 2022年08月09日 02:18/ 0 赞/ 218 阅读

相关剑指offer—-和为S的两个数字

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

末蓝、/ 2022年07月19日 05:20/ 0 赞/ 224 阅读

相关剑指offer 和为S的两个数字

题目描述输入一个递增排序的数组和一个数字S，在数组中查找两个数，是的他们的和正好是S，如果有多对数字的和等于S，输出两个数的乘积最小的。输出描述:对应每个测试案例，输出

待我称王封你为后i/ 2022年05月21日 05:18/ 0 赞/ 221 阅读

相关剑指offer:和为S的两个数字

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

谁借莪１个温暖的怀抱￠/ 2022年04月10日 09:17/ 0 赞/ 228 阅读

相关剑指Offer-和为S的两个数字

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

傷城~/ 2022年02月18日 14:09/ 0 赞/ 245 阅读

相关剑指offer：和为S的两个数字

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

阳光穿透心脏的1/2处/ 2021年12月17日 16:03/ 0 赞/ 280 阅读

相关和为S的两个数字-剑指offer-Java

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

梦里梦外;/ 2021年12月09日 03:29/ 0 赞/ 228 阅读

相关剑指offer：和为S的两个数字

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

深藏阁楼爱情的钟/ 2021年12月09日 01:09/ 0 赞/ 263 阅读