推荐

完整《剑指Offer》算法题解析系列请点击 👉 《剑指Offer》全解析 Java 版

题目描述

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

输出描述

对应每个测试案例,输出两个数,小的先输出。
import java.util.ArrayList;
public class Solution {
   
    public ArrayList<Integer> FindNumbersWithSum(int [] array,int sum) {
   
        
    }
}

思路:

滑动窗口/双指针

一个低位指针指着首位,一个高位指针指着末位。

如果两个指针指着的数字之和小于目标值,则低位指针后移一位;

如果两个指针指着的数字之和大于目标值,则高位指针前移一位;

实现:

import java.util.ArrayList;
public class Solution {
   
    public ArrayList<Integer> FindNumbersWithSum(int [] array,int sum) {
   
        int pLow = 0;
        int pHigh = array.length - 1;
        ArrayList<Integer> list = new ArrayList<>();
        while(pLow < pHigh) {
   
            int count = array[pLow] + array[pHigh];
            if (count == sum) {
   
                list.add(array[pLow]);
                list.add(array[pHigh]);
                return list;
            } else if (count > sum) {
   
                pHigh--;
            } else {
   
                pLow++;
            }
            }
            
            return list;
    }
}

看完之后,如果还有什么不懂的,可以在评论区留言,会及时回答更新。

这里是猿兄,为你分享程序员的世界。

非常感谢各位大佬们能看到这里,如果觉得文章还不错的话, 求点赞👍 求关注💗 求分享👬求评论📝 这些对猿兄来说真的 非常有用!!!

注: 如果猿兄这篇博客有任何错误和建议,欢迎大家留言,不胜感激!