- 检查是否存在满足条件的数字组合（Java JS Python C）)
(新卷,100分)- 检查是否存在满足条件的数字组合（Java & JS & Python & C）
题目描述
给定一个正整数数组，检查数组中是否存在满足规则的数字组合
规则：A = B + 2C
输入描述
第一行输出数组的元素个数。
接下来一行输出所有数组元素，用空格隔开。
输出描述
如果存在满足要求的数，在同一行里依次输出规则里A/B/C的取值，用空格隔开。
如果不存在，输出0。
备注
- 数组长度在3-100之间。
- 数组成员为0-65535，数组成员可以重复，但每个成员只能在结果算式中使用一次。如：数组成员为[0, 0, 1, 5]，0出现2次是允许的，但结果0 = 0 + 2 * 0是不允许的，因为算式中使用了3个0。
- 用例保证每组数字里最多只有一组符合要求的解。
用例
| 输入 | 4 |
| 输出 | 7 3 2 |
| 说明 | 7 = 3 + 2 * 2 |
| 输入 | 3 1 1 1 |
| 输出 | 0 |
| 说明 | 找不到满足条件的组合 |
题目解析
由于数组长度较小（3~100），即使采用三重循环的暴力解法也不会超时。
解题步骤如下：
- 首先将数组降序排列，这样第一层循环选中的数必然是最大的，可作为A
- 第二层和第三层循环选中的较小数则分别作为B和C（顺序可互换）
备注说明：
- 题目保证每组数字最多只有一组符合条件的解
- 因此一旦找到符合条件的解，即可立即返回结果
Java算法源码
import java.util.Arrays; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = Integer.parseInt(sc.nextLine()); Integer[] arr = Arrays.stream(sc.nextLine().split(" ")).map(Integer::parseInt).toArray(Integer[]::new); System.out.println(getResult(n, arr)); } public static String getResult(int n, Integer[] arr) { Arrays.sort(arr, (a, b) -> b - a); for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { for (int k = j + 1; k < n; k++) { if (arr[i] == arr[j] + 2 * arr[k]) { return arr[i] + " " + arr[j] + " " + arr[k]; } if (arr[i] == arr[k] + 2 * arr[j]) { return arr[i] + " " + arr[k] + " " + arr[j]; } } } } return "0"; } }JS算法源码
/* JavaScript Node ACM模式 控制台输入获取 */ const readline = require("readline"); const rl = readline.createInterface({ input: process.stdin, output: process.stdout, }); const lines = []; rl.on("line", (line) => { lines.push(line); if (lines.length === 2) { let n = parseInt(lines[0]); let arr = lines[1].split(" ").map(Number); console.log(getResult(n, arr)); lines.length = 0; } }); function getResult(n, arr) { arr.sort((a, b) => b - a); for (let i = 0; i < n; i++) { for (let j = i + 1; j < n; j++) { for (let k = j + 1; k < n; k++) { if (arr[i] == arr[j] + 2 * arr[k]) { return `${arr[i]} ${arr[j]} ${arr[k]}`; } if (arr[i] == arr[k] + 2 * arr[j]) { return `${arr[i]} ${arr[k]} ${arr[j]}`; } } } } return "0"; }Python算法源码
# 输入获取 n = int(input()) arr = list(map(int, input().split())) # 算法入口 def getResult(): arr.sort(reverse=True) for i in range(n): for j in range(i + 1, n): for k in range(j + 1, n): if arr[i] == arr[j] + 2 * arr[k]: return f"{arr[i]} {arr[j]} {arr[k]}" if arr[i] == arr[k] + 2 * arr[j]: return f"{arr[i]} {arr[k]} {arr[j]}" return "0" # 算法调用 print(getResult())C算法源码
#include <stdio.h> #include <stdlib.h> int cmp(const void* a, const void* b) { return (*(int*) b) - (*(int*) a); } int main() { int n; scanf("%d", &n); int nums[n]; for(int i=0; i<n; i++) { scanf("%d", &nums[i]); } qsort(nums, n, sizeof(int), cmp); for(int i=0; i<n; i++) { for(int j=i+1; j<n; j++) { for(int k=j+1; k<n; k++) { if(nums[i] == nums[j] + 2 * nums[k]) { printf("%d %d %d\n", nums[i], nums[j], nums[k]); return 0; } if(nums[i] == nums[k] + 2 * nums[j]) { printf("%d %d %d\n", nums[i], nums[k], nums[j]); return 0; } } } } puts("0"); return 0; }
)
