2023年华为OD机试(python)B卷-符合要求的元组的个数-K数之和
2023-12-28 14:05:06
一、题目
题目描述:
给定一个整数数组 nums、一个数字k,一个整数目标值 target,请问nums中是否存在k个元素使得其相加结果为target,请输出所有符合条件且不重复的k元组的个数
数据范围 2 <= nums.length <= 200 -10^9 < numslil <?10^9 -10^9 <?target <?10^9 2<=k<=100
二、输入输出
输入描述:
第一行是nums取值: 2 7 11 15?
第二行是k的取值: 2?
第三行是target取值: 9
输出描述:
输出第一行是符合要求的元组个数: 1
补充说明: [2,7]满足,输出个数是1
三、示例
示例1:
输入:
-1 0 1 2 -1 -4
3
0?
输出:
2?
说明:
?[-1,0,1],[-1,-1,2]满足条件
五、解题思路
直接遍历所有可能性
六、参考代码?
# -*- coding: utf-8 -*-
'''
@File : 2023-B-符合要求的元组的个数-K数之和.py
@Time : 2023/12/28 01:14:28
@Author : mgc
@Version : 1.0
@Desc : None
'''
# import os
# import re
# import sys
# import copy
# import math
# import queue
# import functools
# from queue import Queue
# from collections import Counter, defaultdict
def countKSum(nums, k, target):
nums = sorted(nums) # 对数组进行升序排序
result = 0 # 计数器,用于记录符合条件的k元组的个数
def dfs(pos, sum_val, count):
nonlocal result
if count == k and sum_val == target: # 当已选择的元素个数等于k且总和等于target时,找到一个符合条件的k元组
result += 1
return
i = pos
while i < len(nums):
if i > pos and nums[i - 1] == nums[i]:
i += 1
continue
if count + 1 == k:
if sum_val + nums[i] == target:
result += 1
# 不满足条件时不需要进行额外操作,直接跳过即可
else:
new_pos = i + 1
dfs(new_pos, sum_val + nums[i], count + 1)
i += 1
dfs(0, 0, 0)
return result
# 测试代码
nums = [int(x) for x in input().split(" ")] # 整数数组nums
k = int(input()) # k的取值
target = int(input()) # 目标值target
result = countKSum(nums, k, target)
print(result)
文章来源:https://blog.csdn.net/u014481728/article/details/135258857
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!