原创

【剑指Offer】042——和为S的两个数字 (数值)

题目描述

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

解题思路

法一:哈希法。两个数都是这个集合中的,用一个HashMap,它的 key 存储数S与当前数字的差,value 存储当前的数字,比如S=15, 当前的数为 4,则往 hashmap 中插入(key=11, value=4),11不一定是这个数组中的值。我们遍历数组,判断hashmap 中的 key 是否存在当前数字,如果存在,说明数组存在着另一个数与当前的数相加和为 S,我们就可以判断它们的乘积是否小于之前的乘积,如果小的话就替换之前的找到的数字,如果大就放弃当前找到的。如果hashmap 中的 key 不存在当前的数字,说明还没有找到相加和为 S 的两个数,那就把S与当前数字的差作为 key,当前数字作为 value 插入到 hashmap 中,继续遍历。(这种方法间接解决了多对情况,如果出现第二对和为S,就与之前的less做比较)

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

参考代码

Java

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{
                map.put(sum - array[i], array[i]);
            }
        }
        return res;
    }
    // 左右逼近的方法
    public ArrayList<Integer> FindNumbersWithSum2(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;
    }
}

Python

# -*- coding:utf-8 -*-
class Solution:
    def FindNumbersWithSum(self, array, tsum):
        # write code here
        res = []
        if len(array) < 2:
            return res
        i, j = 0, len(array) - 1
        while i!=j:
            tmp_sum = array[i] + array[j]
            if tmp_sum == tsum:
                res.append(array[i])
                res.append(array[j])
                break
            elif tmp_sum < tsum:
                i += 1
            elif tmp_sum > tsum:
                j -= 1
        return res
正文到此结束
本文目录