每天一道剑指offer-和为S的两个数字

考试结束,班级平均分只拿到了年级第二,班主任于是问道:大家都知道世界第一高峰珠穆朗玛峰,有人知道世界第二高峰是什么吗?正当班主任要继续发话,只听到角落默默响起来一个声音:”乔戈里峰

题目

每天一道剑指offer-和为S的两个数字 https://www.nowcoder.com/questionTerminal/390da4f7a00f44bea7c2f3d19491311b 题目详述 输入一个递增排序的数组和一个数字S,在数组中查找两个数,使得他们的和正好是S,如果有多对数字的和等于S,输出两个数的乘积最小的。

题目详解

思路

数列满足递增,设两个头尾两个指针i和j, 若ai + aj == sum,就是答案(相差越远乘积越小) 若ai + aj > sum,aj肯定不是答案之一(前面已得出 i 前面的数已是不可能),j -= 1 若ai + aj < sum,ai肯定不是答案之一(前面已得出 j 后面的数已是不可能),i += 1

代码

import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> FindNumbersWithSum(int [] array,int sum) {
        ArrayList<Integer> resultList = new ArrayList<>();
        if(array.length <= 1)
            return resultList;
        for(int i=0,j=array.length-1;i<j;)
        {
            if(array[i] + array[j] == sum)
            {
                resultList.add(array[i]);
                resultList.add(array[j]);
                return resultList;//找到直接返回
            }else if(array[i] + array[j] > sum)
            {//和已经大于目标值了,所以大数要减小!
                j--;
            }else{//和小于目标值,所以小数要表大!
                i++;
            }
        }
        return resultList;    

    }
}

结束语

作者乔戈里亲历2019秋招,哈工大计算机本硕,百度java工程师,欢迎大家关注我的微信公众号:程序员乔戈里,公众号有3T编程资源,以及我和我朋友(百度C++工程师)在秋招期间整理的近200M的面试必考的java与C++面经,并有每天一道leetcode打卡群与技术交流群,欢迎关注。

原文发布于微信公众号 - 程序员乔戈里(CXYqiaogeli)

原文发表时间:2019-01-18

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

扫码关注云+社区

领取腾讯云代金券