题目链接

题目描述

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

示例

  1. 输入:
  2. {1,2,3,4,10,11,12,13}  14
  4. 输出：
  5. {1,13}

解题思路

  1. 二分查找的思想
  2. 定义首尾的两个指针，一个指针指向元素较小的值，一个指针指向元素较大的值。
    • 指向较小元素的指针从头向尾遍历，
    • 指向较大元素的指针从尾向头遍历。
  • 如果两个指针指向元素的和 sum == target ，判断乘积大小。用变量保存小的两个数字
  • 如果 sum > target ，移动较大的元素，使 sum 变小一些；

  • 如果 sum < target ，移动较小的元素，使 sum 变大一些。

    代码

    1. /*
    2.   二分查找思想
    3.    */
    4.   public ArrayList<Integer> FindNumbersWithSum(int [] nums,int target) {
    5.       // 必须放在第一行定义，因为判断数组为空，或者找不到合适的数字时，需要返回空的ArrayList
    6.       ArrayList<Integer> arrlist = new ArrayList<>();
    8.       // 判断传入数组为空
    9.       if(nums.length==0 || nums==null){
    10.           return arrlist;
    11.       }
    13.       // 定义首尾的两个指针
    14.       int start=0,end=nums.length-1;
    15.       // 定义用来存放最小乘积
    16.       int minMulti = Integer.MAX_VALUE;
    17.       // 定义两个变量用来存放最小的两个数
    18.       int a=-1,b=-1;
    19.       // 开始遍历
    20.       while(start < end){
    21.           int sum = nums[start] + nums[end];
    22.           if(sum == target){
    23.               int multi = nums[start] * nums[end];
    24.               if(multi < minMulti){
    25.                   a = nums[start];
    26.                   b = nums[end];
    27.                   minMulti = multi;
    28.               }
    29.               // 两端同时收缩
    30.               start++;
    31.               end--;
    32.           }
    33.           // 右侧收缩
    34.           else if(sum > target){
    35.               end--;
    36.           }
    37.           // 左侧收缩
    38.           else if(sum < target){
    39.               start++;
    40.           }
    41.       }
    42.       // 数组中没有找到合适的数字，返回初始定义的空ArrayList
    43.       if(a==-1 || b==-1){
    44.           return arrlist;
    45.       }
    47.       arrlist.add(a);
    48.       arrlist.add(b);
    49.       return arrlist;
    51.   }