首页 > 试题广场 >

和为S的两个数字

[编程题]和为S的两个数字
  • 热度指数：490208 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 64M，其他语言128M
  • 算法知识视频讲解
输入一个升序数组 array 和一个数字S，在数组中查找两个数，使得他们的和正好是S，如果有多对数字的和等于S，返回任意一组即可，如果无法找出这样的数字，返回一个空数组即可。

数据范围: ， 
示例1

输入

[1,2,4,7,11,15],15

输出

[4,11]

说明

返回[4,11]或者[11,4]都是可以的
示例2

输入

[1,5,11],10

输出

[]

说明

不存在，返回空数组
示例3

输入

[1,2,3,4],5

输出

[1,4]

说明

返回[1,4],[4,1],[2,3],[3,2]都是可以的
示例4

输入

[1,2,2,4],4

输出

[2,2]
算法知识视频讲解
开通博客
头像 牛客题解官
发表于 2020-06-01 14:44:20
精华题解 题目的主要信息： 升序数组中找到和为S的两个数字 若有多组，返回任意一组 无法找到则返回空数组 举一反三： 学习完本题的思路你可以解决如下题目： 方法一：哈希表（推荐使用） 知识点：哈希表 哈希表是一种根据关键码（key）直接访问值（value）的一种数据结构。而这种直接访问意味着只要知道k 展开全文
去ta的博客 赞 (30) 回复(13) 收起
头像 漫漫云天自翱翔
发表于 2021-06-19 22:24:45
精华题解 题解一： 暴力解题思路： 双层循环,在确定第一个值array[i]的情况下，遍历其余所有值，找到相匹配的array[j]，找到即可结束循环复杂度分析：时间复杂度： O(n^2)空间复杂度： O(1) class Solution { public: vector<int> Fin 展开全文
去ta的博客 赞 (4) 回复(0) 收起
头像 Maokt
发表于 2021-07-07 17:03:40
精华题解 算法思想一：辅助数组 解题思路： 要求a + b = sum, 如果已知a， 那么b = sum - a 遍历数组设置为a，然后将tmp代替原数组并删除元素a，在新的数组tmp中寻找是否存在 sum-a，最后再通过排序方式查找乘积最小的数据组 图解： 数组array：[1，2 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 鸠摩罗什
发表于 2021-06-20 14:36:28
精华题解 描述        输入一个递增排序的数组和一个数字S，在数组中查找两个数，使得他们的和正好是S，如果有多对数字的和等于S，返回两个数的乘积最小的，如果无法找出这样的数字，返回一个空数组即可。返回值描述 对 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 扣得皮
发表于 2020-01-05 21:21:31
最外层的乘积最小，别被题目误导 import java.util.ArrayList; public class Solution { public ArrayList<Integer> FindNumbersWithSum(int [] array,int sum) { 展开全文
去ta的博客 赞 (71) 回复(1) 收起
头像 秋招拿offer啊
发表于 2019-08-13 18:08:35
和为S的两个数字 题目描述输入一个递增排序的数组和一个数字S，在数组中查找两个数，使得他们的和正好是S，如果有多对数字的和等于S，输出两个数的乘积最小的。输出描述:对应每个测试案例，输出两个数，小的先输出。 联动和为s的连续序列 思路：因为要查找两个数字，使得他们的和为S,而且输出的时候，乘积 展开全文
去ta的博客 赞 (8) 回复(0) 收起
头像 Java小白zzm
发表于 2020-02-17 23:43:37
同样的思路双指针法，我发现排序数组分析一般都用这个方法 public ArrayList<Integer> FindNumbersWithSum(int [] array,int sum) { ArrayList<Integer> res= new Arra 展开全文
去ta的博客 赞 (7) 回复(4) 收起
头像 ccจุ๊บ
发表于 2020-02-15 20:35:52
思路：x+y = tsum ，那么y = tsum -x ，只需要遍历array，for x in array，判断tsum-x 是否in array即可。有的话加入列表中。array遍历结束后，用内置的sort进行排序即可 # -*- coding:utf-8 -*- class Solution 展开全文
去ta的博客 赞 (3) 回复(2) 收起
头像 ssssxt
发表于 2020-06-03 16:29:02
https://leetcode-cn.com/problems/he-wei-sde-liang-ge-shu-zi-lcof/ 题目描述 输入一个递增排序的数组和一个数字s，在数组中查找两个数，使得它们的和正好是s。如果有多对数字的和等于s，则输出任意一对即可。 示例 1： 输入：nums = 展开全文
去ta的博客 赞 (3) 回复(0) 收起
头像 Killian.M
发表于 2020-06-25 11:24:37
首先想到的还是hashmap 具体思路很简单，将所有值放入map的value部分，因为可能有重复，所以不能放在key部分。 这里使用Map.Entry的方式进行遍历，效率会高点。遍历的同时判断map是否有这个value和sum-value；如果有就更新temp，当然首先清空list，再放入新的元素。 展开全文
去ta的博客 赞 (2) 回复(1) 收起
头像 大大萌阳
发表于 2020-02-23 16:44:19
题目描述输入一个递增排序的数组和一个数字S，在数组中查找两个数，使得他们的和正好是S，如果有多对数字的和等于S，输出两个数的乘积最小的。 刚开始看见题目第一反应就是用双指针，后来看见说要输出两个数的乘积最小的，这个时候就被题干迷惑了，初始化了一个二维数组，将每一对满足要求的数字添加到该二维数组中，可 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 Freeverc
发表于 2020-04-15 23:12:56
和为S的两个数字O(logn * logn)解法 题目描述 输入一个递增排序的数组和一个数字S，在数组中查找两个数，使得他们的和正好是S，如果有多对数字的和等于S，输出两个数的乘积最小的。 输出描述: 对应每个测试案例，输出两个数，小的先输出。 解法 1. 穷举： 对所有数据对都查找一遍时间复杂度： 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 LaN666
发表于 2021-01-30 22:05:36
直接使用双指针，只是题目多加了一个限定，输出乘积最小的那一组。 public ArrayList<Integer> FindNumbersWithSum(int [] array,int sum) { int l = 0, r = array.length-1; 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 面向工资编程的大三小白
发表于 2020-07-24 15:10:06
题目描述输入一个递增排序的数组和一个数字S，在数组中查找两个数，使得他们的和正好是S，如果有多对数字的和等于S，输出两个数的乘积最小的。 输出描述:对应每个测试案例，输出两个数，小的先输出。 思路：先读题，发现递增的话不会有重复数字，如果有多对数字的和为s，可以用数学证明一个最小的数和最大的数的乘积 展开全文
去ta的博客 赞 (2) 回复(0) 收起

问题信息

数组 数学 双指针
来自：“一战通offer”互...
难度：
1271条回答 97462浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号