【哈希表】2024E-跳房子I
【哈希表】2024E-跳房子I
2月20日修改
本文讨论了“2024E-跳房子I”这一算法题目，介绍其题目描述、输入输出要求、解题思路、代码实现及时空复杂度。关键要点包括：
1.
题目描述：给定每回合可能的跳步步数数组和房子总格数，需找出索引和最小的步数组合，使小红两回合跳到最后一格，数组元素不可重复使用。
2.
输入输出处理：输入的数组字符串需切片去掉中括号再处理；输出答案要按特定格式，逗号后无空格，ACM模式判题严格。
3.
索引和最小值初始化：设置变量min_idx_sum表示索引和，初始化为len(nums)*2 ，方便后续找到更小的索引和。
4.
寻找索引和最小值：遍历数组，结合哈希表，当找到两数之和为目标值且索引和小于当前最小索引和时，更新答案和最小索引和。
5.
不能提前退出：不能在首次找到符合要求的答案时就退出循环，可能错过索引和更小的正确结果。
6.
代码实现：给出Python、Java、C++三种语言的代码实现。
7.
时空复杂度：时间复杂度为O(N)，仅需一次遍历数组；空间复杂度为O(N)，由哈希表所占空间决定 。
题目描述与示例
题目描述
跳房子，也叫跳飞机，是一种世界性的儿童游戏。 游戏参与者需要分多个回合按顺序跳到第1格直到房子的最后一格
跳房子的过程中，可以向前跳，也可以向后跳。
假设房子的总格数是count，小红每回合可能连续跳的步教都放在数组steps中，请问数组中是否有一种步数的组合，可以让小红两个回合跳到最后一格? 如果有，请输出索引和最小的步数组合。
注意:
•
数组中的步数可以重复，但数组中的元素不能重复使用。
•
提供的数据保证存在满足题目要求的组合，且索引和最小的步数组合是唯一的。
输入描述
第一行输入为每回合可能连续跳的步数，它是整数数组类型。
第二行输入为房子总格数count，它是int整数类型。
输出描述
返回索引和最小的满足要求的步数组合(顺序保持steps中原有顺序)
备注
•
count ≤ 1000