剑指offer: 和为S的两个数字

秒速五厘米 2023-07-18 14:26 68阅读 0赞

##### 1. 题目描述 #####

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

**输出描述：**

> 输出所有和为S的连续正数序列。序列内按照从小至大的顺序，序列间按照开始数字从>小到大的顺序

原题传送门：[link][].

##### 2. 提取关键词 #####

滑动窗口

##### 3. 思路 #####

*  数列满足递增，设两个头尾两个指针i和j，

1.  若ai + aj == sum，就是答案（相差越远乘积越小）
2.  若ai + aj > sum，aj肯定不是答案之一（前面已得出 i 前面的数已是不可能），j -= 1
3.  若ai + aj < sum，ai肯定不是答案之一（前面已得出 j 后面的数已是不可能），i += 1

*  **辅助理解**：如果寻找 1，2，3，4，5中满足和是7的乘机最小的两个数。

1.  i=1，j=5。那么此时i=1和最大数之和都不能满足条件，那么i=1一定不符合条件。
2.  所以i++，依次类推
3.  最后得到答案

##### 4. 代码（Java） #####

import java.util.ArrayList;
    public class Solution {
        public ArrayList<Integer> FindNumbersWithSum(int [] array,int sum) {
            //定义线性表
            ArrayList<Integer> list = new ArrayList<Integer>();
            //定义
            if (array == null || array.length < 2) {
                
                return list;
            }
            //定义表头表尾两个指针
            int i=0,j=array.length-1;
            //表头表尾不重叠进行循环
            while(i<j){
                //因为相差越远乘积越小，如果出现第一个满足条件的就是答案，直接返回。
                if(array[i]+array[j]==sum){
                list.add(array[i]);
                list.add(array[j]);
                    return list;
                 //设定左右指针不能回头
                 //如果和大于sum 表尾指针左移动，如果和小于sum 表头指针右移动。
               }else if(array[i]+array[j]>sum){
                    j--;
                }else{
                    i++;
                }
                 
            }
            return list;
        }
    }

##### 5.复杂度 #####

*  O(n)

##### 6. 知识积累 #####

*  暂无

[link]: https://www.nowcoder.com/practice/c451a3fd84b64cb19485dad758a55ebe?tpId=13&tqId=11194&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking