文章目录

1、题目描述2、解题思路3、解题代码4、解题心得

1、题目描述

  【JZ42】输入一个递增排序的数组和一个数字S，在数组中查找两个数，使得他们的和正好是S，如果有多对数字的和等于S，输出两个数的乘积最小的。   知识点：数学，数组，双指针。   难度：☆

2、解题思路

  注意到本题的关键信息：递增排序。   定义两个指针i和j，开始分别指向头和尾。   这里包含一个数学原理，对于一个递增序列来说，外部两个数的乘积肯定小于内部两个数的乘积。比如一个序列是{1,2,3,4,5,6,7}，1+7=3+5，但是1×7＜3×5。   也就是说，i和j分别从两边向中间靠近，只要出现满足arr[i] == arr[j]的i和j，就是答案。

3、解题代码

package pers.klb.jzoffer.medium; import java.util.ArrayList; /** * @program: JzOffer2021 * @description: 和为Sum的两个数 * @author: Meumax * @create: 2020-06-27 19:21 **/ public class FindTwoNumbers { public ArrayList<Integer> FindNumbersWithSum(int[] array, int sum) { // 如果array没有数字，返回空的ArrayList if (array.length == 0) { return new ArrayList<>(); } ArrayList<Integer> list = new ArrayList<>(); // 定义两个索引来指向array的元素，i为头，j为尾 int i = 0; int j = array.length - 1; // 如果i和j的前后关系变了，即遍历结束 while (i < j) { // 找到目标 if (array[i] + array[j] == sum) { list.add(array[i]); list.add(array[j]); break; } // 偏大了，把j索引往小调整一下 if (array[i] + array[j] > sum) { j--; } // 偏小了，把i索引往大调整一下 // 判断要加上 i < j ，因为上面j调整后可能越界 if (i < j && array[i] + array[j] < sum) { i++; } } // 返回 return list; } }

  时间复杂度：O(N)   空间复杂的：O(1)

4、解题心得

  本题难度较低，关键是抓住“递增排序”这个关键信息，同时得有一定的数学常识，对于递增序列，和相同的两个数，外部的乘积小于内部。