首页 > 试题广场 >

和为S的两个数字

[编程题]和为S的两个数字

热度指数：494726 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

输入一个递增排序的数组array和一个数字S，在数组中查找两个数，使得他们的和正好是S，如果有多对数字的和等于S，返回任意一组即可，如果无法找出这样的数字，返回一个空数组即可。

数据范围:

0<=len(array)<=10⁵

1<=array[i]<=10⁶

示例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]都是可以的

算法知识视频讲解

查看答案及解析

推荐

马客(Mark)

数列满足递增，设两个头尾两个指针i和j，

若ai + aj == sum，就是答案（相差越远乘积越小）

若ai + aj > sum，aj肯定不是答案之一（前面已得出 i 前面的数已是不可能），j -= 1

若ai + aj < sum，ai肯定不是答案之一（前面已得出 j 后面的数已是不可能），i += 1

O(n)

typedef vector<int> vi;
class Solution {
public:
    vi FindNumbersWithSum(const vi& a,int sum) {
        vi res;
        int n = a.size();
        int i = 0, j = n - 1;
        while(i < j){
            if(a[i] + a[j] == sum){
                res.push_back(a[i]);
                res.push_back(a[j]);
                break;
            }
            while(i < j && a[i] + a[j] > sum) --j;
            while(i < j && a[i] + a[j] < sum) ++i;
        }
        return res;
    }
};

编辑于 2016-08-03 15:52:48 回复(80)

Python

牛客492090284号

# -*- coding:utf-8 -*-
class Solution:
def FindNumbersWithSum(self, array, tsum):
# write code here
for i in array:
array.remove(i)
if tsum-i in array:
return [i, tsum-i]

return []

这个解法牛逼

发表于 2021-06-21 23:14:16 回复(0)

Python

两个头一个大

class Solution:
def FindNumbersWithSum(self, array, tsum):
# write code here
tmp = []
for i, a in enumerate(array):
if tsum - a in array[i + 1:]:
tmp.append(a)
tmp.append(tsum - a)
return tmp[:2]

发表于 2021-06-08 13:51:38 回复(0)

Python

牛客541273514号

# -*- coding:utf-8 -*-
class Solution:
    def FindNumbersWithSum(self, array, tsum):
        # write code here
        if len(array)<2:
            return []
        res=[]
        n=len(array)
        for i in range(n-1):
            for j in range(i+1,n):
                if array[i]+array[j]==tsum:
                    res.append([array[i],array[j]])
        if len(res)==0:
            return []
        thre=res[0][0]*res[0][1]
        out=res[0]
        for item in res:
            if item[0]*item[1]<thre:
                thre=item[0]*item[1]
                out=item
        return out

发表于 2021-05-03 01:15:33 回复(0)

Python

Hiroi

Python写出所有和为S的组合，再计算乘积进行比较。

# -*- coding:utf-8 -*-
class Solution:
    def FindNumbersWithSum(self, array, tsum):
        # write code here
        results = []
        for i in range(len(array)-1):
            for j in range(i+1,len(array)):
                if array[i]+array[j]==tsum:
                    temp = []
                    temp.append(array[i])
                    temp.append(array[j])
                    if temp not in results:
                        results.append(temp)
        if len(results)==0:
            return results
        elif len(results)==1:
            return results[0]
        else:
            multi = []
            for res in results:
                multi.append(res[0]*res[1])
            idx = multi.index(min(multi))
            return results[idx]

发表于 2021-04-17 21:16:14 回复(0)

Python

鸢公子

# -*- coding:utf-8 -*-
class Solution:
def FindNumbersWithSum(self, array, tsum):
for i, a in enumerate(array):
if tsum - a in array[i + 1:]:
return a, tsum - a
return []

发表于 2021-02-20 14:19:54 回复(0)

Python

在下小6

python解法：hash法和双指针法；

# # -*- coding:utf-8 -*-
# """
# 思路1:用hash数组，看差值在不在数组中，在的话再比较乘积的大小；
# """
# class Solution:
#     def FindNumbersWithSum(self, array, tsum):
#         if len(array) == 0:
#             return []
#         hash = {}
#         m,n,min = 0,0,array[len(array)-1]*array[len(array)-1]
#         for i,num in enumerate(array):
#             hash[num] = i
#         for i,num in enumerate(array):
#             j = hash.get(tsum-num)
#             if j is not None and i != j:
#                 res = num*array[j]
#                 if (res<min):
#                     min = res
#                     m = array[i]
#                     n = array[j]
#         # 没找到两个元素和为目标值；
#         if m == 0 & n == 0:
#             return []
#         return [m,n]

# """
# 思路2:优化思路1的遍历部分，但是影响好像不大，hhhh；
# """
# class Solution:
#     def FindNumbersWithSum(self, array, tsum):
#         if len(array) == 0:
#             return []
#         hash = {}
#         m,n,min = 0,0,array[len(array)-1]*array[len(array)-1]
#         for i,num in enumerate(array):
#             hash[num] = i
#         for i,num in enumerate(array):
#             # 优化部分
#             if i <= len(array) // 2:
#                 j = hash.get(tsum-num)
#                 if j is not None and i != j:
#                     res = num*array[j]
#                     if (res<min):
#                         min = res
#                         m = array[i]
#                         n = array[j]
#         # 没找到两个元素和为目标值；
#         if m == 0 & n == 0:
#             return []
#         return [m,n]

# """
# 思路3:hash，不用比较乘积的大小，因为递增数组有a[0]*a[n]<=a[1]*a[n-1];
# """
# class Solution:
#     def FindNumbersWithSum(self, array, tsum):
#         if len(array) == 0:
#             return []
#         hash = {}
#         for i,num in enumerate(array):
#             hash[num] = i
#         for i,num in enumerate(array):
#             if i <= len(array) // 2:
#                 j = hash.get(tsum-num)
#                 if j is not None and i != j:
#                     return [array[i],array[j]]
#         # 没找到两个元素和为目标值；
#         return []

"""
思路4:双指针：递增数组有a[0]*a[n]<=a[1]*a[n-1]，同样不用比较乘积大小
a[i]+a[j]>tsum,j--
a[i]+a[j]<tsum,i++
"""
class Solution:
    def FindNumbersWithSum(self, array, tsum):
        if len(array) == 0:
            return []
        i,j = 0,len(array)-1
        while(i<j):
            if array[i] + array[j] == tsum:
                return[array[i],array[j]]
            elif array[i] + array[j] > tsum:
                j -= 1
            else:
                i += 1
        # 没找到两个元素和为目标值；
        return []

编辑于 2021-02-18 15:39:51 回复(0)

Python

牛客623389398号

class Solution:
    def FindNumbersWithSum(self, array, tsum):
        # write code here
        if not array:
            return []
        for a in array:
            b = tsum-a 
            if b in array:
                if a<b:
                    return [a,b] 
                else:
                    return [b,a]
            else:
                continue 
        return []

发表于 2020-10-28 13:11:10 回复(1)

Python

老和山小学生

# -*- coding:utf-8 -*-
class Solution:
    def FindNumbersWithSum(self, array, tsum):
        # write code here
        i = 0
        j = len(array)-1
        while i < j:
            if array[i] + array[j] > tsum:
                j -= 1
            elif array[i] + array[j] < tsum:
                i += 1
            else:
                return array[i], array[j]
        return []

发表于 2020-10-16 13:28:27 回复(0)

Python

BJ-2020

思路:夹逼准则
一头一尾两个指针，相加>目标：右指针前进一位
相加<目标：左指针前进一位
相等则输出
找不到则不存在

class Solution:
    def FindNumbersWithSum(self, array, tsum):
        # write code here
        if not array:
            return []
        n = len(array)
        i = 0
        j = n -1 
        while i < j:
            if array[i] + array[j]< tsum:
                i += 1
            elif array[i] + array[j]> tsum:
                j -= 1
            elif array[i] + array[j] == tsum:
                return array[i],array[j]
        return []

发表于 2020-09-11 19:22:59 回复(0)

Python

火树银花zjl

class Solution:
    def FindNumbersWithSum(self, array, tsum):
        # write code here
        if len(array)<=1:
            return []
        res=[]
        ans=[]
        for i in range(len(array)):
            for j in range(i+1,len(array)):
                if array[i]+array[j]==tsum:
                    res.append(array[i]*array[j])
                    ans.append([array[i],array[j]])
        if len(res)==0:
            return []
        else:
            b=res.index(min(res))
            return ans[b]

发表于 2020-09-11 13:31:18 回复(0)

Python

将来的前端工程师

本题还是沿用了上一题dfs的思想，就是去判断当前循环数和后面数相加是否为n，最后再通过对结果数组循环得到结果

# -*- coding:utf-8 -*-
class Solution:
    def FindNumbersWithSum(self, p, n):
        # write code here
        def dfs(p,index,total,n,res):
            if len(res) == total:
                if sum(res) == n:
                    arr.append([i for i in res])
                return
            for i in range(index,len(p)):
                res.append(p[i])
                dfs(p,i+1,total,n,res)
                res.pop()
        arr = []
        dfs(p,0,2,n,[])
        if arr == []:
            return []
        MIN = arr[0][0] * arr[0][1]
        minIndex = 0
        for i in range(len(arr)):
            if MIN > arr[i][0] * arr[i][1]:
                minIndex = i
                MIN = arr[i][0] * arr[i][1]
        return arr[minIndex]

发表于 2020-08-27 00:51:52 回复(0)

Python

DDooo

# -*- coding:utf-8 -*-
class Solution:
    def FindNumbersWithSum(self, array, tsum):
        # write code here
        s = []
        for i in array:
            s.append(tsum - i)
        for j in s:
            if j in array:
                return (tsum-j,j)
        return []

此题技巧：序列递增，所以如果输出的话，一定是第一个满足条件的i,j，此时return出来的就是第一个满足条件的了。

先遍历array中的i,将j = sum-i存入数组s中，然后遍历j是否也在原array中，第一在原array中的j和他对应的i就是题目所求了！

发表于 2020-07-26 19:16:54 回复(0)

Python

CrucioLzy

class Solution:
    def FindNumbersWithSum(self, array, tsum):
        # write code here
        new_array = array
        for i in array:
            if i > tsum:
                new_array = array[:i]
        result = []
        j = len(new_array) - 1
        for i in range(len(new_array)):
            while j > i:
                if new_array[i]+new_array[j] == tsum:
                    result.append(([new_array[i],new_array[j],j]))
                    j-=1
                    # j不用回到最右 从当前点左移一格开始继续就行
                    break
                else:
                    j-=1
            if i == j:
                if result:
                    #如果已经找到一个点了，在i增大的情况下，j肯定要比已找到的j更小
                    j = result[-1][2] - 1
                else:
                    #没找到点的话j从最右
                    j = len(new_array) - 1
        if len(result) == 0:
            return []
        else:
            return result[0][:2]

先排出单个数比tsum大的（看了别人讨论的答案以后发现这一步可能有些多余）

得到一个新的array 最大值一定是小于tsum的，才有可能两个数加起来等于tsum

接下来设置收尾指针各一个，i 从前往后遍历，j从后往前遍历寻找符合的项

最小乘积，易知i,j差最大的时候乘积最小，result 里面第一个点就是

发表于 2020-07-16 12:16:53 回复(0)

Python

一直爬的蜗牛

# -*- coding:utf-8 -*-
class Solution:
    def FindNumbersWithSum(self, array, tsum):
        # write code here
        #如果有多对数字和等于S，两个数的差越大，乘积越小
        n = len(array)
        low = 0
        high = n-1
        while low < high:
            if array[low] + array[high] == tsum:
                return array[low],array[high]
            elif array[low] + array[high] > tsum:
                high -= 1
            else:
                low += 1
        return []

编辑于 2020-06-17 23:06:47 回复(1)

Python

牛客770473387号

# -*- coding:utf-8 -*-
class Solution:
def FindNumbersWithSum(self, array, tsum):
# write code here
list1 = []
list2 = []
for a in range(len(array)):
for b in range(a+1,len(array)):
dataa = array[a]
datab = array[b]
if dataa + datab == tsum:
list1.append([dataa,datab])
list2.append(dataa*datab)
else:
pass
if len(list2) == 0:
return []
data = min(list2)
index = list2.index(data)
return list1[index]

发表于 2020-06-17 17:12:38 回复(0)

Python

牛客624277366号

# -*- coding:utf-8 -*-
class Solution:
    def FindNumbersWithSum(self, array, tsum):
        # write code here
        l = []
        p = []
        d = {}
        for i in range(0, len(array)):
            for j in range(i+1, len(array)):

                if array[i] + array[j] == tsum:
                    l.append([array[i], array[j]])
                    p.append(array[i]*array[j])
                else:
                    continue
        if len(p) != 0:
            for i in range(0, len(p)):
                d[p[i]] = l[i]
            p.sort()
            return d[p[0]]
        else:
            return []

发表于 2020-05-28 14:21:15 回复(0)

Python

Kuriyamaaa

# -*- coding:utf-8 -*-
class Solution:
    def FindNumbersWithSum(self, array, tsum):
        S=tsum
        A=array
        if len(A)<=1:
            return []
        if len(A)==2:
            if A[0]+A[1]==S:
                return A
        re=[]
        for i in range(len(A)-1):
            for j in range(i+1,len(A)):
                if A[i]+A[j]==S:
                    re=[A[i],A[j]]
                    return re
        return re
                
        # write code here

发表于 2020-05-27 15:57:23 回复(0)

Python

橘子汽水超人2号

# -*- coding:utf-8 -*-
class Solution:
    def FindNumbersWithSum(self, array, tsum):
        # write code here
        for i in array:
            array.remove(i)
            if (tsum-i) in array:
                return [i,tsum-i]
        return []

尝试提交

编辑于 2020-05-17 13:59:50 回复(0)

Python

牛客341441072号

class Solution:
    def FindNumbersWithSum(self, array, tsum):
        # write code here
        dicts = {}
        res1 = []
        res2 = []
        for i in range(len(array)):
            num = tsum - array[i]
            if num not in dicts:
                dicts[array[i]] = num
            else:
                res1.append([num,dicts[num]])
                res2.append(dicts[num]*num)
        if res1==[]:
            return []
        else:
            mins = min(res2)
            return res1[res2.index(mins)]

发表于 2020-04-30 16:01:17 回复(0)

提交观点

问题信息

数组数学双指针

来自：“一战通offer”互...

难度：

87条回答 843收藏 106445浏览

通过挑战的用户

查看代码

Elastic...

2023-02-25 22:47:48
牛客71194...

2022-09-16 15:27:36
大金毛_

2022-09-16 11:30:22
远方不姓方

2022-09-16 10:39:10
ৡ晨ꦿ᭄࿐

2022-09-16 09:49:19

和为S的两个数字

输入

输出

说明

输入

输出

说明

输入

输出

说明

问题信息

热门推荐

通过挑战的用户

相关试题