题⽬描述

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

返回值描述：对应每个测试案例，输出两个数，⼩的先输出。

输⼊：[1,2,4,7,11,15],15
返回值：[4,11]

思路及解答

暴⼒遍历

直接遍历每两个数，查看其和是否符合等于 sum ,再计算其乘积，是否⼩于之前的乘积，如果⼩于，则更新。

public ArrayList FindNumbersWithSum(int[] array, int sum) {
     ArrayList results = new ArrayList();
     long mutip = 999999999;
     if (array != null && array.length > 2) {
         for (int i = 0; i  sum) {
                 	break;
                 }
             }
         }
     }
     return results;
 }

• 时间复杂度：O(n²)，需要检查所有可能的数对组合
• 空间复杂度：O(1)，只使用常数级别额外空间

使⽤HashSet

针对每⼀个数字 a ，都查看 hashset 中是否存在 sum-a ，同时把该数字添加到 set 中。如果存在则计算其乘积，更新乘积最⼩值。

public ArrayList FindNumbersWithSum1(int[] array, int sum) {
     ArrayList results = new ArrayList();
     long mutip = 999999999;
     HashSet set = new HashSet();
     if (array != null && array.length > 2) {
         for (int i = 0; i 

• 时间复杂度：O(n)，只需遍历数组一次
• 空间复杂度：O(n)，需要HashSet存储元素

双指针法（最优）

利用数组有序特性：左右指针分别指向数组首尾，根据当前和动态调整指针位置

由于数组 nums[] 是有序的，也就是第⼀个数字是最⼩的，第⼆个数字是最⼤的，那么我们使⽤⼀个指针 i 指向数组第⼀个元素，⼀个指针 j 指向数组最后⼀个元素。

i 指针往右边移动， j 指针往左边移动，直到两者相撞（相等）。

如果 nums[i]+nums[j] == sum ,那么说明这个是可能存在的解，需要计算两者的乘积，如果⽐保存的乘积还⼩，则更新结果。同时左边指针 i 往右边移动⼀位，右边指针 j 往左边移动⼀位。

如果 nums[i] + nums[j] > sum ,则说明和太⼤了，⽐ sum 还要⼤，则右边的指针j需要左移⼀步，即是 j-- 。

如果 nums[i] + nums[j]

public ArrayList FindNumbersWithSum2(int[] array, int sum) {
     ArrayList results = new ArrayList();
     long mutip = 999999999;
     if (array != null && array.length > 2) {
         int left = 0,right = array.length-1;
         while(leftsum){
                 right--;
             }else{
                 left++;
             }
         }
     }
     return results;
 }

• 时间复杂度：O(n)，最坏情况下左右指针共同遍历整个数组
• 空间复杂度：O(1)，只使用固定数量的指针变量

本文来自在线网站：seven的菜鸟成长之路，作者：seven，转载请注明原文链接：www.seven97.top