[剑指offer] 和为S的两个数字

题目描述

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

解题思路

法一:哈希法。用一个HashMap,它的 key 存储数S与数组中每个数的差,value 存储当前的数字,比较S=15, 当前的数为 4,则往 hashmap 中插入(key=11, value=4)。我们遍历数组,判断hashmap 中的 key 是否存在当前的数字,如果存在,说明存在着另一个数与当前的数相加和为 S,我们就可以判断它们的乘积是否小于之前的乘积,如果小的话就替换之前的找到的数字,如果大就放弃当前找到的。如果hashmap 中的 key 不存在当前的数字,说明还没有找到相加和为 S 的两个数,那就把S与当前数字的差作为 key,当前数字作为 value 插入到 hashmap 中,继续遍历。

法二:左右夹逼的方法。a+b=sum,a和b越远乘积越小,因为数组是递增排序,所以一头一尾两个指针往内靠近的方法找到的就是乘积最小的情况。 若ai + aj == sum,就是答案(相差越远乘积越小) 若ai + aj > sum,说明 aj 太大了,j — 若ai + aj < sum,说明 ai 太小了,i ++

参考代码

import java.util.ArrayList;
import java.util.HashMap;
public class Solution {
    public ArrayList<Integer> FindNumbersWithSum(int [] array,int sum) {
        ArrayList<Integer> res = new ArrayList<Integer>();
        if(array.length < 2)
            return res;
        HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
        int less = Integer.MAX_VALUE;
        for(int i = 0; i < array.length; i++){
            if(map.containsKey(array[i])){
                if(array[i] * map.get(array[i]) < less){
                    less = array[i] * map.get(array[i]);
                    res.clear();
                    res.add(map.get(array[i]));
                    res.add(array[i]);
                }
            }else{
                int key = sum - array[i];
                map.put(key, array[i]);
            }
        }
        return res;
    }
}

法二:左右夹逼

import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> FindNumbersWithSum(int [] array,int sum) {
        ArrayList<Integer> res = new ArrayList<Integer>();
        if(array.length < 2)
            return res;
        int i = 0, j = array.length - 1;
        while(i != j){
            if(array[i] + array[j] == sum){
                res.add(array[i]);
                res.add(array[j]);
                break;
            }else if(array[i] + array[j] < sum){
                i++;
            }else{
                j--;
            }
        }
        return res;
    }
}

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏趣谈编程

一文读懂Java泛型中的通配符 ?

之前不太明白泛型中通配符"?"的含义,直到我在网上发现了Jakob Jenkov的一篇文章,觉得很不错,所以翻译过来,大家也可以点击文末左下角的阅读原文看英文版...

1293
来自专栏用户3030674的专栏

java集合的操作(set,Iterator)

Iterator、Collection、Set和HashSet关系  Iterator<——Collection<——Set<——HashSet  Iterat...

2833
来自专栏玄魂工作室

Python黑帽编程2.2 数值类型

Python黑帽编程2.2 数值类型 数值类型,说白了就是处理各种各样的数字,Python中的数值类型包括整型、长整型、布尔、双精度浮点、十进制浮点和复数,这...

2969
来自专栏Python爱好者

Java基础笔记15

1688
来自专栏青玉伏案

JavaSE高级之集合类

​下面的内容是对java中的集合类进行的总结,过段时间会分享java的网路编程,多线程等内容,欢迎批评指正。 1.Java中的集合是用来存放对象的,即集合是对象...

2419
来自专栏积累沉淀

Google 面试题分析 | 字典里面的最长单词

描述 给定一个字符串列表words,找到words最长的word,使得这个word可用words中的其他word一次一个字符地构建。如果有多个可选答案,则返回最...

2056
来自专栏彭湖湾的编程世界

【数据结构】实现字典API:有序数组和无序链表

参考资料 《算法(java)》                           — — Robert Sedgewick, Kevin Wayne 《数据结...

3335
来自专栏待你如初见

Day12

1675
来自专栏用户3030674的专栏

java集合框架(hashSet自定义元素是否相同,重写hashCode和equals方法)

/*HashSet 基本操作 * --set:元素是无序的,存入和取出顺序不一致,元素不可以重复 * (通过哈希值来判断是否是同一个对象) * ---...

1622
来自专栏Ryan Miao

java中List对象列表去重或取出以及排序

面试碰到几次list的去重和排序。下面介绍一种做法: 1. list去重 1.1 实体类Student List<Student>容量10k以上,要求去重复。这...

7939

扫码关注云+社区

领取腾讯云代金券