给定一个整数数组,判断其中是否有3个数和为N

[编程题]给定一个整数数组,判断其中是否有3个数和为N

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

输入描述:

输入为一行
逗号前为一个整数数组，每个元素间用空格隔开；逗号后为N

输出描述:

输出bool值
True表示存在3个和为N的数
False表示不存在3个和为N的数

示例1

输入

1 2 3 4 5,10

输出

True

备注:

数组长度不超过2000，所以数均为int范围的正整数

算法知识视频讲解

Python

白色纯度

# -*- coding:utf-8 -*-
def find(numbers,key):
    record = []
    dirc = {}
    for i in range(len(numbers)): #用哈希表换来O(n^2)的时间复杂度
        if key-numbers[i] in dirc:
            dirc[key-numbers[i]] += [i]
        else:
            dirc[key-numbers[i]] = [i]
    for i in range(len(numbers)-1):
        for j in range(i+1,len(numbers)):
            if numbers[i] + numbers[j] in dirc:
                if i not in dirc[numbers[i] + numbers[j]] and j not in dirc[numbers[i] + numbers[j]]:
                    return True
    return False
if __name__=="__main__":
    num = input().split(",")
    numbers = [int(i) for i in num[0].split()]
    key = int(num[-1])
    print(find(numbers, key))

发表于 2019-07-04 11:10:54 回复(0)