【双指针】2023C-跳房子II
【双指针】2023C-跳房子II
[P3004] 【双指针】2023C-跳房子II
本题练习地址：https://www.algomooc.com/problem/P3004
题目练习网址：https://www.algomooc.com/problem/P3004
题目描述与示例
题目描述
跳房子，也叫跳飞机，是一种世界性的儿童游戏。
游戏参与者需要分多个回合按顺序跳到第1格直到房子的最后一格，然后获得一次选房子的机会，直到所有房子都被选完，房子最多的人获胜。
跳房子的过程中，如果有踩线等违规行为会结束当前回合，甚至可能倒退几步。
假设房子的总格数是count，小红每回合可能连续跳的步数都放在数据steps中，请问数组中是否有一种步数的组合，可以让小红三个回合跳到最后一格？如果有，请输出索引和最小的步数组合，数据保证索引和最小的步数组合是唯一的。
注意：数组中的步数可以重复，但数组中的元素不能重复使用。
输入描述
第一行输入为房子总格数count，它是整数类型int。
第二行输入为每回合可能连续跳过的步数，它是整数数组类型。
输出描述
返回索引和最小满足要求的步数组合。
注意：顺序保持steps中的原有顺序。
备注
- count <= 10000；
- 3 <= steps.length <= 10000；
- -100000 <= steps[i] <= 100000；
示例一
输入
1,4,5,2,0,2
9输出
4,5,0说明
示例二
输入
1,5,2,0,2,4
9输出
5,2,2示例三
输入
-1,2,4,9
12输出
-1,4,9解题思路
注意，本题和LeetCode15、三数之和基本完全一致。区别仅仅在于本题需要找到下标和最小的索引。
代码
Python
# 题目：2024E-跳房子II
# 分值：100
# 作者：许老师-闭着眼睛学数理化
# 算法：相向双指针
# 代码看不懂的地方，请直接在群上提问
from math import inf
# 输入原数组lst
lst = list(map(int, input().split(",")))
# 输入目标和
target = int(input())
# 获得原数组长度n
n = len(lst)
# 对原nums数组进行排序，同时需要记录在原数组中的下标i，作为排序的第二个依据
nums = sorted((num, i) for i, num in enumerate(lst))
# 初始化一个长度为3的数组，用于储存三个数的下标，初始化均为inf
ans_idx = [inf, inf, inf]
# 考虑第一个数first
for i, (first, idx) in enumerate(nums[:-2]):
# 如果发现第i、第i+1、第i+2个数的和加起来超过target
# 则更靠后的的选择肯定和更大，直接退出循环
if nums[i][0] + nums[i+1][0] + nums[i+2][0] > target:
break
# 去重操作，如果遇到连续两个数相等，那么考虑nums[i]和考虑nums[i-1]所作的计算是一样的
# 直接跳过nums[i]的计算
if i != 0 and nums[i][0] == nums[i-1][0]:
continue
# 构建相向双指针left和right
left, right = i+1, n-1
while left < right:
# 计算三个数的和
sum3 = first + nums[left][0] + nums[right][0]
# 三数和太大，right左移
if sum3 > target:
right -= 1
# 三数和太小，left右移
elif sum3 < target:
left += 1
# 三数和等于target，如果三个下标和比之前记录过的三数下标和更小
# 则更新ans_idx
else:
if sum(ans_idx) > idx + nums[left][1] + nums[right][1]:
ans_idx = [idx, nums[left][1], nums[right][1]]
# 注意此处，只需要写right -= 1就行，不需要加上left += 1
# 1. 只写right -= 1就可以保证代码不会陷入死循环
# 因为只需要保证每一个if分支中，至少有一个指针是在变化的（也就是我们选择的right）
# 那么while中的left < right条件就一定会有不成立的时候
# 2. 由于排序时先按照num大小排列，再按照num在原数组中的索引排列。
# 如果此时存在 nums[right-1][0] == nums[right][0]
# 那么nums[right-1][1]会小于nums[right][1]
# i, nums[left][1]和nums[right-1][1]可以构成更小的索引和
# 如果加上了left += 1，可能会漏算全局最小的索引和
right -= 1
# 退出循环，ans_idx为在原数组中的三个数的下标
# 答案需要按照下标大小进行排列
ans_idx.sort()
ans = ",".join(str(lst[idx]) for idx in ans_idx)
print(ans)Java
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
// 读取一行包含逗号分隔数字的数组
String line = scanner.nextLine();
// 使用 StringTokenizer 分割数字
StringTokenizer tokenizer = new StringTokenizer(line, ",");
List<Integer> lst = new ArrayList<>();
while (tokenizer.hasMoreTokens()) {
lst.add(Integer.parseInt(tokenizer.nextToken()));
}
// 读取下一行的数字
int target = scanner.nextInt();
// 获得原数组长度 n
int n = lst.size();
// 对原 nums 数组进行排序，同时需要记录在原数组中的下标 i，作为排序的第二个依据
List<Pair> nums = new ArrayList<>();
for (int i = 0; i < n; i++) {
nums.add(new Pair(lst.get(i), i));
}
Collections.sort(nums);
// 初始化一个长度为 3 的数组，用于储存三个数的下标，初始化均为 n
List<Integer> ansIdx = new ArrayList<>(Arrays.asList(n, n, n));
// 考虑第一个数 first
for (int i = 0; i < n - 2; i++) {
// 如果发现第 i、第 i+1、第 i+2 个数的和加起来超过 target
// 则更靠后的选择肯定和更大，直接退出循环
if (nums.get(i).first + nums.get(i + 1).first + nums.get(i + 2).first > target) {
break;
}
// 去重操作，如果遇到连续两个数相等，那么考虑 nums[i] 和考虑 nums[i-1] 所作的计算是一样的
// 直接跳过 nums[i] 的计算
if (i != 0 && nums.get(i).first == nums.get(i - 1).first) {
continue;
}
// 构建相向双指针 left 和 right
int left = i + 1, right = n - 1;
while (left < right) {
// 计算三个数的和
int sum3 = nums.get(i).first + nums.get(left).first + nums.get(right).first;
// 三数和太大，right 左移
if (sum3 > target) {
right--;
}
// 三数和太小，left 右移
else if (sum3 < target) {
left++;
}
// 三数和等于 target，如果三个下标和比之前记录过的三数下标和更小
// 则更新 ansIdx
else {
if (ansIdx.get(0) + ansIdx.get(1) + ansIdx.get(2) > nums.get(i).second + nums.get(left).second + nums.get(right).second) {
ansIdx = Arrays.asList(nums.get(i).second, nums.get(left).second, nums.get(right).second);
}
// 注意此处，只需要写 righ-- 就行，不需要加上 left++
// 1. 只写right -= 1就可以保证代码不会陷入死循环
// 因为只需要保证每一个if分支中，至少有一个指针是在变化的（也就是我们选择的right）
// 那么while中的left < right条件就一定会有不成立的时候
// 2. 由于排序时先按照num大小排列，再按照num在原数组中的索引排列。
// 如果此时存在 nums[right-1][0] == nums[right][0]
// 那么nums[right-1][1]会小于nums[right][1]
// i, nums[left][1]和nums[right-1][1]可以构成更小的索引和
// 如果加上了 left++ ，可能会漏算全局最小的索引和
right--;
}
}
}
// 退出循环，ansIdx 为在原数组中的三个数的下标
// 答案需要按照下标大小进行排列
Collections.sort(ansIdx);
for (int i = 0; i < 3; i++) {
System.out.print(lst.get(ansIdx.get(i)));
if (i < 2) {
System.out.print(",");
}
}
System.out.println();
}
static class Pair implements Comparable<Pair> {
int first;
int second;
Pair(int first, int second) {
this.first = first;
this.second = second;
}
@Override
public int compareTo(Pair other) {
return Integer.compare(this.first, other.first);
}
}
}C++
#include <iostream>
#include <sstream>
#include <vector>
#include <algorithm>
#include <numeric>
using namespace std;
int main() {
// 读取一行包含逗号分隔数字的数组
string line;
getline(cin, line);
// 使用 stringstream 分割数字
stringstream ss(line);
vector<int> lst;
string token;
while(getline(ss, token,','))
{
lst.push_back(stoi(token));
}
// 读取下一行的数字
int target;
cin >> target;
// 获得原数组长度 n
int n = lst.size();
// 对原 nums 数组进行排序，同时需要记录在原数组中的下标 i，作为排序的第二个依据
vector<pair<int, int>> nums;
for (int i = 0; i < n; i++) {
nums.push_back({lst[i], i});
}
sort(nums.begin(), nums.end());
// 初始化一个长度为 3 的数组，用于储存三个数的下标，初始化均为 n
vector<int> ansIdx(3, n);
// 考虑第一个数 first
for (int i = 0; i < n - 2; i++) {
// 如果发现第 i、第 i+1、第 i+2 个数的和加起来超过 target
// 则更靠后的选择肯定和更大，直接退出循环
if (nums[i].first + nums[i + 1].first + nums[i + 2].first > target) {
break;
}
// 去重操作，如果遇到连续两个数相等，那么考虑 nums[i] 和考虑 nums[i-1] 所作的计算是一样的
// 直接跳过 nums[i] 的计算
if (i != 0 && nums[i].first == nums[i - 1].first) {
continue;
}
// 构建相向双指针 left 和 right
int left = i + 1, right = n - 1;
while (left < right) {
// 计算三个数的和
int sum3 = nums[i].first + nums[left].first + nums[right].first;
// 三数和太大，right 左移
if (sum3 > target) {
right--;
}
// 三数和太小，left 右移
else if (sum3 < target) {
left++;
}
// 三数和等于 target，如果三个下标和比之前记录过的三数下标和更小
// 则更新 ansIdx
else {
if (accumulate(ansIdx.begin(), ansIdx.end(), 0) > nums[i].second + nums[left].second + nums[right].second) {
ansIdx = {nums[i].second, nums[left].second, nums[right].second};
}
// 注意此处，只需要写 righ-- 就行，不需要加上 left++
// 1. 只写right -= 1就可以保证代码不会陷入死循环
// 因为只需要保证每一个if分支中，至少有一个指针是在变化的（也就是我们选择的right）
// 那么while中的left < right条件就一定会有不成立的时候
// 2. 由于排序时先按照num大小排列，再按照num在原数组中的索引排列。
// 如果此时存在 nums[right-1][0] == nums[right][0]
// 那么nums[right-1][1]会小于nums[right][1]
// i, nums[left][1]和nums[right-1][1]可以构成更小的索引和
// 如果加上了 left++ ，可能会漏算全局最小的索引和
right--;
}
}
}
// 退出循环，ansIdx 为在原数组中的三个数的下标
// 答案需要按照下标大小进行排列
sort(ansIdx.begin(), ansIdx.end());
for (int i = 0; i < 3; i++) {
cout << lst[ansIdx[i]];
if (i < 2) {
cout << ",";
}
}
cout << endl;
return 0;
}C
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include <string.h>
// 定义结构体用于存储数值和下标
typedef struct {
int value;
int index;
} Pair;
// 比较函数，用于排序
int compare(const void *a, const void *b) {
Pair *p1 = (Pair *)a;
Pair *p2 = (Pair *)b;
if (p1->value != p2->value) {
return p1->value - p2->value;
}
return p1->index - p2->index;
}
int main() {
// 输入原数组
char input[10000];
if (!fgets(input, sizeof(input), stdin)) {
fprintf(stderr, "Error reading input\n");
return 1;
}
int lst[1000], n = 0, target;
char *token = strtok(input, ",");
while (token != NULL) {
if (n >= 1000) {
fprintf(stderr, "Input exceeds maximum array size\n");
return 1;
}
lst[n++] = atoi(token);
token = strtok(NULL, ",");
}
// 输入目标和
if (scanf("%d", &target) != 1) {
fprintf(stderr, "Error reading target\n");
return 1;
}
// 检查是否有足够的元素
if (n < 3) {
fprintf(stderr, "Not enough elements in input\n");
return 1;
}
// 构建一个Pair数组用于存储数值和下标
Pair nums[1000];
for (int i = 0; i < n; i++) {
nums[i].value = lst[i];
nums[i].index = i;
}
// 对nums数组按值和下标排序
qsort(nums, n, sizeof(Pair), compare);
// 初始化用于存储答案的下标数组
int ans_idx[3] = {INT_MAX, INT_MAX, INT_MAX};
// 遍历第一个数
for (int i = 0; i < n - 2; i++) {
// 如果三数之和超过目标和，退出循环
if (nums[i].value + nums[i + 1].value + nums[i + 2].value > target) {
break;
}
// 去重操作
if (i > 0 && nums[i].value == nums[i - 1].value) {
continue;
}
// 双指针初始化
int left = i + 1, right = n - 1;
while (left < right) {
int sum3 = nums[i].value + nums[left].value + nums[right].value;
if (sum3 > target) {
right--;
} else if (sum3 < target) {
left++;
} else {
// 如果当前索引和更小，则更新答案
if (nums[i].index + nums[left].index + nums[right].index <
ans_idx[0] + ans_idx[1] + ans_idx[2]) {
ans_idx[0] = nums[i].index;
ans_idx[1] = nums[left].index;
ans_idx[2] = nums[right].index;
}
// 注意此处，只需要写 righ-- 就行，不需要加上 left++
// 1. 只写right -= 1就可以保证代码不会陷入死循环
// 因为只需要保证每一个if分支中，至少有一个指针是在变化的（也就是我们选择的right）
// 那么while中的left < right条件就一定会有不成立的时候
// 2. 由于排序时先按照num大小排列，再按照num在原数组中的索引排列。
// 如果此时存在 nums[right-1][0] == nums[right][0]
// 那么nums[right-1][1]会小于nums[right][1]
// i, nums[left][1]和nums[right-1][1]可以构成更小的索引和
// 如果加上了 left++ ，可能会漏算全局最小的索引和
right--;
}
}
}
// 如果没有找到答案，直接退出
if (ans_idx[0] == INT_MAX) {
return 1;
}
// 按下标大小排序
for (int i = 0; i < 2; i++) {
for (int j = 0; j < 2 - i; j++) {
if (ans_idx[j] > ans_idx[j + 1]) {
int temp = ans_idx[j];
ans_idx[j] = ans_idx[j + 1];
ans_idx[j + 1] = temp;
}
}
}
// 输出答案
printf("%d,%d,%d\n", lst[ans_idx[0]], lst[ans_idx[1]], lst[ans_idx[2]]);
return 0;
}Node JavaScript
// 导入必要的模块
const readline = require("readline");
// 创建输入接口
const rl = readline.createInterface({
input: process.stdin,
output: process.stdout,
});
rl.question("", (line1) => {
rl.question("", (line2) => {
const lst = line1.split(",").map(Number); // 读取并解析输入数组
const target = parseInt(line2); // 读取目标和
const n = lst.length; // 获取数组长度
// 对原数组进行排序，同时记录下标
const nums = lst
.map((num, i) => ({ num, index: i }))
.sort((a, b) => a.num - b.num || a.index - b.index);
// 初始化用于存储三个数下标的数组，初始值为正无穷
let ansIdx = [Infinity, Infinity, Infinity];
// 遍历第一个数
for (let i = 0; i < n - 2; i++) {
const first = nums[i].num;
const idx = nums[i].index;
// 如果当前三个数的最小和已经超过目标值，直接退出循环
if (nums[i].num + nums[i + 1].num + nums[i + 2].num > target) {
break;
}
// 去重操作，跳过连续相同的数字
if (i > 0 && nums[i].num === nums[i - 1].num) {
continue;
}
// 双指针初始化
let left = i + 1,
right = n - 1;
while (left < right) {
const sum3 = first + nums[left].num + nums[right].num;
if (sum3 > target) {
right--;
} else if (sum3 < target) {
left++;
} else {
// 如果当前索引和更小，更新答案
const candidateIdx = [idx, nums[left].index, nums[right].index];
const candidateSum = candidateIdx.reduce((a, b) => a + b, 0);
const currentSum = ansIdx.reduce((a, b) => a + b, 0);
if (candidateSum < currentSum) {
ansIdx = candidateIdx;
}
// 注意此处，只需要写 righ-- 就行，不需要加上 left++
// 1. 只写right -= 1就可以保证代码不会陷入死循环
// 因为只需要保证每一个if分支中，至少有一个指针是在变化的（也就是我们选择的right）
// 那么while中的left < right条件就一定会有不成立的时候
// 2. 由于排序时先按照num大小排列，再按照num在原数组中的索引排列。
// 如果此时存在 nums[right-1][0] == nums[right][0]
// 那么nums[right-1][1]会小于nums[right][1]
// i, nums[left][1]和nums[right-1][1]可以构成更小的索引和
// 如果加上了 left++ ，可能会漏算全局最小的索引和
right--;
}
}
}
// 按照下标排序
ansIdx.sort((a, b) => a - b);
// 输出结果
console.log(ansIdx.map((idx) => lst[idx]).join(","));
rl.close();
});
});Go
package main
import (
"bufio"
"fmt"
"os"
"sort"
"strconv"
"strings"
)
type Pair struct {
Num int
Index int
}
func main() {
reader := bufio.NewReader(os.Stdin)
line1, _ := reader.ReadString('\n')
line1 = strings.TrimSpace(line1)
line2, _ := reader.ReadString('\n')
line2 = strings.TrimSpace(line2)
// 解析输入
strNums := strings.Split(line1, ",")
lst := make([]int, len(strNums))
for i, s := range strNums {
lst[i], _ = strconv.Atoi(s)
}
target, _ := strconv.Atoi(line2)
n := len(lst)
// 对原数组进行排序，同时记录下标
nums := make([]Pair, n)
for i := 0; i < n; i++ {
nums[i] = Pair{Num: lst[i], Index: i}
}
sort.Slice(nums, func(i, j int) bool {
if nums[i].Num == nums[j].Num {
return nums[i].Index < nums[j].Index
}
return nums[i].Num < nums[j].Num
})
// 初始化用于存储三个数下标的数组，初始值为正无穷
ansIdx := []int{1 << 30, 1 << 30, 1 << 30}
// 遍历第一个数
for i := 0; i < n-2; i++ {
first := nums[i].Num
idx := nums[i].Index
// 如果当前三个数的最小和已经超过目标值，直接退出循环
if nums[i].Num+nums[i+1].Num+nums[i+2].Num > target {
break
}
// 去重操作，跳过连续相同的数字
if i > 0 && nums[i].Num == nums[i-1].Num {
continue
}
// 双指针初始化
left, right := i+1, n-1
for left < right {
sum3 := first + nums[left].Num + nums[right].Num
if sum3 > target {
right--
} else if sum3 < target {
left++
} else {
// 如果当前索引和更小，更新答案
candidateIdx := []int{idx, nums[left].Index, nums[right].Index}
candidateSum := candidateIdx[0] + candidateIdx[1] + candidateIdx[2]
currentSum := ansIdx[0] + ansIdx[1] + ansIdx[2]
if candidateSum < currentSum {
ansIdx = candidateIdx
}
// 注意此处，只需要写 righ-- 就行，不需要加上 left++
// 1. 只写right -= 1就可以保证代码不会陷入死循环
// 因为只需要保证每一个if分支中，至少有一个指针是在变化的（也就是我们选择的right）
// 那么while中的left < right条件就一定会有不成立的时候
// 2. 由于排序时先按照num大小排列，再按照num在原数组中的索引排列。
// 如果此时存在 nums[right-1][0] == nums[right][0]
// 那么nums[right-1][1]会小于nums[right][1]
// i, nums[left][1]和nums[right-1][1]可以构成更小的索引和
// 如果加上了 left++ ，可能会漏算全局最小的索引和
right--
}
}
}
// 按照下标排序
sort.Ints(ansIdx)
// 输出结果
fmt.Printf("%d,%d,%d\n", lst[ansIdx[0]], lst[ansIdx[1]], lst[ansIdx[2]])
}时空复杂度
时间复杂度：O(``n^2``)。双重循环所需时间复杂度。
空间复杂度：O(``n``)。列表nums所占空间。