题目描述
给定一个整数数组 nums、一个数字k,一个整数目标值 target,请问nums中是否存在k个元素使得其相加结果为target,请输出所有符合条件且不重复的k元组的个数
数据范围
- 2 ≤ nums.length ≤ 200
- -10^9 ≤ nums[i] ≤ 10^9
- -10^9 ≤ target ≤ 10^9
- 2 ≤ k ≤ 100
输入描述
第一行是nums取值:2 7 11 15
第二行是k的取值:2
第三行是target取值:9
输出描述
输出第一行是符合要求的元组个数:1
补充说明:[2,7]满足,输出个数是1
用例
输入 |
-1 0 1 2 -1 -4 3 0 |
输出 |
2 |
说明 |
[-1,0,1],[-1,-1,2]满足条件 |
输入 |
2 7 11 15 2 9 |
输出 |
1 |
说明 |
[2,7]符合条件 |
题目解析
本题其实需要参考:
LeetCode - 15 三数之和
LeetCode - 18 四数之和
这两题。如果你对这两题不熟悉,请做本题前,先做完前面这两题,这两题是基础。否则下面代码会看不懂。
其中三数之和,是需要固定三元组中的最小的一个值,然后通过双指针找到剩余两个数。
其中四数之和,是需要固定四元组中的最小的两个值,然后通过双指针找到剩余两个数。
而K数之和,其实需要固定K元组中最小的K-2个值,然后通过双指针找到剩余两个数。
因此,下面代码实现中分为了两部分:
K-2重for循环完成 K元组中最小的K-2个值的确定
通过双指针完成剩余两个值的确定
而实际上K的值是不确定的,因此第1部分的K-2重for循环需要通过递归完成。
Java代码
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int m = sc.nextInt();
int n = sc.nextInt();
int[][] matrix = new int[m][n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
matrix[i][j] = sc.nextInt();
}
}
System.out.println(getResult(m, n, matrix));
}
public static int getResult(int m, int n, int[][] matrix) {
int count = 0;
int[][] offsets = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};
for (int x = 0; x < m; x++) {
for (int y = 0; y < n; y++) {
if (matrix[x][y] == 1) {
count++;
continue;
}
for (int[] offset : offsets) {
int newX = x + offset[0];
int newY = y + offset[1];
if (newX >= 0 && newX < m && newY >= 0 && newY < n && matrix[newX][newY] == 1) {
count++;
break;
}
}
}
}
return count;
}
}
JS代码
/* JavaScript Node ACM模式 控制台输入获取 */
const rl = require("readline").createInterface({
input: process.stdin,
});
const lines = [];
let m, n;
rl.on("line", (line) => {
lines.push(line);
if (lines.length === 1) {
[m, n] = lines[0].split(" ").map(Number);
}
if (m && lines.length == m + 1) {
lines.shift();
const matrix = lines.map((line) => line.split(" ").map(Number));
console.log(getResult(matrix, m, n));
lines.length = 0;
}
});
function getResult(matrix, m, n) {
let count = 0;
const offsets = [
[-1, 0],
[1, 0],
[0, -1],
[0, 1],
];
for (let x = 0; x < m; x++) {
for (let y = 0; y < n; y++) {
if (matrix[x][y] === 1) {
count++;
continue;
}
for (let [offsetX, offsetY] of offsets) {
const newX = x + offsetX;
const newY = y + offsetY;
if (
newX >= 0 &&
newX < m &&
newY >= 0 &&
newY < n &&
matrix[newX][newY] === 1
) {
count++;
break;
}
}
}
}
return count;
}
Python代码
# 输入获取
m, n = map(int, input().split())
matrix = [list(map(int, input().split())) for _ in range(m)]
# 算法入口
def getResult():
count = 0
offsets = ((-1, 0), (1, 0), (0, -1), (0, 1))
for x in range(m):
for y in range(n):
if matrix[x][y] == 1:
count += 1
continue
for offsetX, offsetY in offsets:
newX = x + offsetX
newY = y + offsetY
if m > newX >= 0 and n > newY >= 0 and matrix[newX][newY] == 1:
count += 1
break
return count
# 算法调用
print(getResult())