剑指OfferJZ42：和为S的两个数字-java版

￡神魔★判官ぃ 2022-08-31 05:56 26阅读 0赞

### 剑指OfferJZ42：和为S的两个数字-java版 ###

*   *   *   *  JZ42：输入一个递增排序的数组和一个数字S，在数组中查找两个数，使得他们的和正好是S，如果有多对数字的和等于S，返回两个数的乘积最小的，如果无法找出这样的数字，返回一个空数组即可

#### JZ42：输入一个递增排序的数组和一个数字S，在数组中查找两个数，使得他们的和正好是S，如果有多对数字的和等于S，返回两个数的乘积最小的，如果无法找出这样的数字，返回一个空数组即可 ####

![在这里插入图片描述][858321d0d89345bcb8d757477d4bb8ed.png]

**首先在数组中找到两个数和为数字S的**  
在递增排序的数组中，（如果不是有序数组需要变成有序的有利于查找）  
设置两个指针，**首（左）指针l**和**尾（右）指针r**，分别位于数组的头部和尾部  
在查找的过程中**指针l往右移动**（往数值大的方向移动），**指针r往左移动**（往数值小的方向移动）

*  如果 左指针指向的数+右指针指向的数=数字S，那么同时将左指针往左移（增大数值），右指针往左移（减小数值），继续进行循环操作直到左右指针位置相邻为止
 *  如果 左指针指向的数+右指针指向的数<数字S，那么将左指针往右移（增大数值），继续进行循环操作直到左右指针位置相邻为止
 *  如果 左指针指向的数+右指针指向的数>数字S，那么将右指针往左移（减小数值），继续进行循环操作直到左右指针位置相邻为止

**如图**：1+10=11小于S，需要将左指针往右移（增大数值）

*  接着2+10=12等于S，满足条件，将这两个数存起来，同时将左指针往左移（增大数值），右指针往左移（减小数值）
 *  接着4+9=13大于S，需要将右指针往左移（减小数值）
 *  接着4+8=12等于S，满足条件，将这两个数存起来，同时将左指针往左移（增大数值），右指针往左移（减小数值）
 *  接着5+6=11小于S，这时发现左指针和右指针位置相邻，结束循环  
    查出来满足两个数和等于数字S的有两对，2和10,4和8

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTk5MjAyMQ_size_16_color_FFFFFF_t_70]

**接着考虑如果有多对数字的和等于S，返回两个数的乘积最小的**  
假设在上一步找到的和为S的数组中，其中一个数是x，那么另一个数就是S-x，两个数的乘积就为x\*（S-x）= -x2+xS  
可以看出两个数的乘积是数学中一个开口向下的二次函数

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTk5MjAyMQ_size_16_color_FFFFFF_t_70 1]

根据两个数在数组中的位置分布，可以判断出左指针指向的数（x）在S/2的左边，右指针指向的数（S-x）在S/2的右边，图像上的数值代表两个数的乘积  
从图中可以看出，S/2左边图像的数值随横坐标的增大而增大，S/2右边图像的数值随横坐标的增大而减小，所以当x离S/2越远（数值越小），S-x离S/2越远（数值越大）时，x和S-x的乘积越大

所以**我们可以得出结论：当左指针指向的数x越小，右指针指向的数x越大，也就是我们第一次找到的那对和为S的数字时，这两个数的乘积是最小的**  
因此在上面查找数组中两个数和为数字S的过程中，**如果 左指针指向的数+右指针指向的数=数字S，那么我们就可以直接返回这两个数字，不用再继续查找了 break循环；**

public class jz42{ 
        public ArrayList<Integer> FindNumbersWithSum(int [] array, int sum) { 
            ArrayList<Integer> list=new ArrayList<>();
            int l=0;//头指针
            int r=array.length-1;//尾指针
    
            while(l<=r-l){ 
                if(array[l]+array[r]==sum) { 
                    list.add(array[l]);
                    list.add(array[r]);
                    break;//第一次找到的两个数便是乘积最小的
                }else if(array[l]+array[r]<sum){ 
                    l++;//将左指针往右移（增大数值）
                }else{ 
                    r--;//将右指针往左移（减小数值）
                }
            }
            return list;
        }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTk5MjAyMQ_size_16_color_FFFFFF_t_70 2]

![在这里插入图片描述][28fe3b3e5e694c879063faf5c8439c8c.png_pic_center]

[858321d0d89345bcb8d757477d4bb8ed.png]: /images/20220829/7626a275686b47b29b560f628f0fe59c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTk5MjAyMQ_size_16_color_FFFFFF_t_70]: /images/20220829/82c9682093374518b5a8bb7c21d7efd4.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTk5MjAyMQ_size_16_color_FFFFFF_t_70 1]: /images/20220829/3e1bccdbe8944e438debe379168f6ea5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTk5MjAyMQ_size_16_color_FFFFFF_t_70 2]: /images/20220829/aaa2115ab1a54fb3b7b594a12ae3a4a2.png
[28fe3b3e5e694c879063faf5c8439c8c.png_pic_center]: /images/20220829/f213d7d5db8d4cd5aa3ed40fe0084f7e.png