剑指offer试题编程练习40(java) 输入一个递增排序的数组和一个数字S，在数组中查找两个数，使得他们的和正好是S，如果有多对数字的和等于S，输出两个数的乘积最小的。

最新推荐文章于 2024-12-01 23:52:34 发布

原创最新推荐文章于 2024-12-01 23:52:34 发布 · 279 阅读

1 ·

CC 4.0 BY-SA版权

文章标签：

#java

数据结构与算法专栏收录该内容

39 篇文章

订阅专栏

本文介绍了一种算法，用于在递增排序的数组中查找两个数，使它们的和等于给定的数字S，并在多个解决方案中选择乘积最小的一对。该算法首先找到所有可能的数对，然后通过比较乘积来确定最佳结果。

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

import java.util.ArrayList;
public class Solution {
 public ArrayList<Integer> FindNumbersWithSum(int [] array,int sum) {
    	ArrayList<Integer> result = new ArrayList<>();
        ArrayList<ArrayList<Integer>> a = new ArrayList<ArrayList<Integer>>();
        if(array.length==0){
            return result;
        }
        if(array[0]>sum){
            return result;
        }
        int s = sum;
        //得到所有可能结果
        for(int i=0;i<array.length-1;i++){
            ArrayList<Integer> b = new ArrayList<>();
            b.add(array[i]);
            sum = sum-array[i];
            for(int j=i+1;j<array.length;j++){
                if(sum==array[j]){
                    b.add(array[j]);
                    a.add(b);
                    sum = s;
                    break;
                }
                if(array[j]>sum){
                    sum = s;
                    break;
                }
            }
        }
        //遍历所有结果，计算乘积，返回最小结果
        int multi = 0;
        int index = 0;
        int m = 0;
        if (a.size() == 0) {
	    return result;
	} else {
        for(int i=0;i<a.size();i++){
            m=a.get(i).get(0)*a.get(i).get(1);
        	if (m<multi) {
        	    index=i;
        	    multi=m;
		} 
            }
        }
        return a.get(index);
    }
}