跳房子I

题目描述

跳房子, 也叫跳飞机, 是一种世界性的儿童游戏.

游戏参与者需要分多个回合按顺序跳到第1格直到房子的最后一格.

跳房子的过程中, 可以向前跳, 也可以向后跳.

假设房子的总格数是count, 小红每回合可能连续跳的步教都放在数组steps中, 请问数组中是否有一种步数的组合, 可以让小红两个回合跳到量后一格?

如果有, 请输出索引和最小的步数组合.

注意:

• 数组中的步数可以重复, 但数组中的元素不能重复使用
• 提供的数据保证存在满足题目要求的组合, 且索引和最小的步数组合是唯一的

输入描述

• 第一行输入为每回合可能连续跳的步数, 它是int整数数组类型.
• 第二行输入为房子总格数count, 它是int整数类型.

备注:

• count ≤ 1000
• 0 ≤ steps.length ≤ 5000
• -100000000 ≤ steps ≤ 100000000

输出描述

返回索引和最小的满足要求的步数组合 (顺序保持steps中原有顺序).

示例1

输入:

[1,4,5,2,2]
7

输出:

[5, 2]

示例2

输入:

[-1,2,4,9,6]
8

输出:

[-1, 9]

题解

Python

def main():
    # 读取输入
    steps_str = input()
    steps = list(map(int, steps_str[1:-1].split(",")))
    assert 0 <= len(steps) <= 5000
    count = int(input())
    assert 0 < count <= 1000

    # 所谓的两步, 就是两数之和等于 count
    # 直接遍历, 或者先生成一个字典, 加快搜索
    min_index = 10 ** 9
    ans = []
    for i in range(len(steps) - 1):
        for j in range(i + 1, len(steps)):
            # 两数之和等于 count
            # 并且两数索引之和更小
            if steps[i] + steps[j] == count and i + j < min_index:
                min_index = min(min_index, i + j)
                ans = [steps[i], steps[j]]
            # 忽略掉后面的步骤
            if i + j > min_index:
                break

        # 忽略掉后面的步骤
        if i + i > min_index:
            break

    # 打印结果
    print("[%d, %d]" % (ans[0], ans[1]))

if __name__ == "__main__":
    main()