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

101 阅读 0 评论 67 点赞

我是靠谱客的博主自然黑猫，最近开发中收集的这篇文章主要介绍剑指offer——会了这题offer就稳了，输入一个递增排序的数组和一个数字S，在数组中查找两个数，使得他们的和正好是S，如果有多对数字的和等于S，输出两个数的乘积最小的。，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

以后闲来无事做可以在牛客网上刷刷一下编程题，今天刷到了一题有关数组的题目，记忆中有同学在面试中被问到了，话不多说，先看题，题目如下：

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

像这种算法题，真的不建议一上来就巴拉巴拉开始写代码，最主要的还是先要明白题目的意思，理清思路，然后在编程。这道算法题我觉得就是一个很典型的例子。很多同学看到题目，可能就在纠结，和为S，先遍历数组呀，然后用一个临时变量去存储满足和为S的两个数的乘积，还要保存这两个数的角标，感觉就不好实现，就算实现了，复杂度肯定也不低。

其实，在拿到算法题之前，我们可以先先分析题目，先尝试着去用数学的思维去看能不能找到突破口。像这个题目，很明显“递增排序的数组”“两个乘积最小”，要想一个递增的数列中两个数乘积最小，那么满足和为S的几组数中，肯定是差值最大的那组数，他们的乘积是最小的（高中数学里面知识）。这样这个题目就变的很简单了，我们只需定义两个指针，一个指向头，一个指向尾，判断头尾指针数组的元素之和跟S去比较，知道等于S，输出这两数a,b，很明显ab的乘积就是最小的。

具体代码如下：

/**
	 * @param 输入一个递增的数组
	 * @param 输入和为S
	 * @return 返回
	 */
	private static ArrayList<Integer> FindNumbersWithSum(int[] array, int sum) {
		ArrayList<Integer> arrayList = new ArrayList<Integer>();
		int head=0,tail = array.length-1;  //定义一个头指针，一个尾指针
		//直到头指针大于尾指针时，退出循环
		while (head<tail) {
			//采用两段到中间夹逼的方式，查找满足条件的数  
			if ((array[head]+array[tail])>sum) {
				tail--;
			}	
			else if ((array[head]+array[tail])<sum) {
				head++;
			}else    
			{
				//一旦满足条件，则ab的乘积一定是最小的，直接退出循环即可。
				arrayList.add(array[head]);
				arrayList.add(array[tail]);
				break;
			}
		}
		return arrayList;
	}

这道算法题很简单，只是一个单纯的数组相关的题目。当然在面试中我们被问到这么简单的原题，可能性不大，但是狡猾的面试官也可能以此简单题为模板去考验我们，这样既会让你感觉到题目似曾相识，还会让你感觉到云里雾里。

如果将上述题目改编一下，聪明的小伙伴们还会做吗？如题：

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

这道题很明显是上道题的变种题，但是有了上面题目的经验，做这道题也不是很难，题目让我们求3个数的乘积最小值，又是递增数组，那能否将三个数abc（其中a<b<c）的乘积最小值，变为a*min(bc)呢？很明显是可以的。当我们将a确定时，这道题就跟上面一样的，也就等价为：当两个数满足和为（S-a），当bc乘积最小时，求b、c。

也就是说，我们只需遍历数组，确定a值，然后bc的值可以转换为上面两个数的方法去解决。只不过现在的头指针不是从0开始，而是从a的角标后一位开始。

代码如下：

	/**
	 * @param array	输入一个递增的数组
	 * @param sum	输入和为S
	 * @return
	 */
	private static ArrayList<Integer> FindThreeWithSum(int[] array, int sum) {
		ArrayList<Integer> arrayList;
		ArrayList<Integer> resultList = new ArrayList<Integer>();
		for (int i = 0; i < array.length; i++) {
			arrayList = FindTwoNumbersWithSum(array,i,sum-array[i]);  //一旦其中一个数确定，剩余两个数的和sum-array[i]也随之确定
			if (!arrayList.isEmpty()) {
				resultList.add(array[i]);
				resultList.addAll(arrayList);
				break;
			}
		}
		return resultList;
	}

	/**
	 * @param array	输入一个递增的数组
	 * @param i		数组角标i为头指针
	 * @param sum	输入和为S
	 * @return  两个数乘积的最小值时，存有两个数的集合
	 */
	private static ArrayList<Integer> FindTwoNumbersWithSum(int[] array,int i, int sum) {
		ArrayList<Integer> arrayList = new ArrayList<Integer>();
		int head=i,tail = array.length-1;  //定义一个头指针，一个尾指针
		//直到头指针大于尾指针时，退出循环
		while (head<tail) {
			//采用两段到中间夹逼的方式，查找满足条件的数  
			if ((array[head]+array[tail])>sum) {
				tail--;
			}	
			else if ((array[head]+array[tail])<sum) {
				head++;
			}else    
			{
				//一旦满足条件，则ab的乘积一定是最小的，直接退出循环即可。
				arrayList.add(array[head]);
				arrayList.add(array[tail]);
				break;
			}
		}
		return arrayList;
	}

代码仅供参考，第一次写博客，请各位多指正吧，写博客的习惯希望自己能坚持吧。以后会不断更新剑指offer与LeetCode里面一些我觉得有意思的题目。