当前位置： 2024华为OD机试题库 (B卷,100分)- 符合要求的元组的个数（Java & JS & Python & C）

(B卷,100分)- 符合要求的元组的个数（Java & JS & Python & C）

2024-05-07 15

题目描述

给定一个整数数组 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]符合条件

题目解析（分治递归+双指针）

本题其实就是要求K数之和。

本题的K数之和，和是存在区别的，

本题的要求的K元组是从整数数组中选取的，这里的整数数组，既可能包含正数，也可能包含负数，也可能包含0，另外最终求得的符合要求的K元组，还要进行去重。

因此，本题无法参考：LintCode – 89 K数之和_伏城之外的博客-CSDN博客

本题其实需要参考：

LeetCode – 15 三数之和_伏城之外的博客-CSDN博客

LeetCode – 18 四数之和_伏城之外的博客-CSDN博客

这两题。如果你对这两题不熟悉，请做本题前，先做完前面这两题，这两题是基础。否则下面代码会看不懂。

其中三数之和，是需要固定三元组中的最小的一个值，然后通过双指针找到剩余两个数。

其中四数之和，是需要固定四元组中的最小的两个值，然后通过双指针找到剩余两个数。

而K数之和，其实需要固定K元组中最小的K-2个值，然后通过双指针找到剩余两个数。

因此，下面代码实现中分为了两部分：

  1. K-2重for循环完成 K元组中最小的K-2个值的确定
  2. 通过双指针完成剩余两个值的确定

而实际上K的值是不确定的，因此第1部分的K-2重for循环需要通过递归完成。

具体请看下面代码实现。

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 == 3) {
    const nums = lines[0].split(" ").map(Number);
    const k = parseInt(lines[1]);
    const target = parseInt(lines[2]);

    console.log(getResult(nums, k, target));

    lines.length = 0;
  }
});

function getResult(nums, k, target) {
  if (k > nums.length) return 0;
  nums.sort((a, b) => a - b);
  return kSum(nums, k, target, 0, 0, 0);
}

// k数之和
function kSum(nums, k, target, start, count, sum) {
  if (k < 2) return count;

  if (k == 2) {
    return twoSum(nums, target, start, count, sum);
  }

  for (let i = start; i <= nums.length - k; i++) {
    // 剪枝
    if (nums[i] > 0 && sum + nums[i] > target) break;

    // 去重
    if (i > start && nums[i] == nums[i - 1]) continue;

    count = kSum(nums, k - 1, target, i + 1, count, sum + nums[i]);
  }

  return count;
}

// 两数之和
function twoSum(nums, target, start, count, preSum) {
  let l = start;
  let r = nums.length - 1;

  while (l < r) {
    const sum = preSum + nums[l] + nums[r];

    if (sum > target) {
      r--;
    } else if (sum < target) {
      l++;
    } else {
      count++;
      // 去重
      while (l + 1 < r && nums[l] == nums[l + 1]) l++;
      // 去重
      while (r - 1 > l && nums[r] == nums[r - 1]) r--;
      l++;
      r--;
    }
  }

  return count;
}

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[] nums = Arrays.stream(sc.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();
    int k = Integer.parseInt(sc.nextLine());
    int target = Integer.parseInt(sc.nextLine());

    System.out.println(getResult(nums, k, target));
  }

  public static int getResult(int[] nums, int k, int target) {
    if (k > nums.length) return 0;
    Arrays.sort(nums);
    return kSum(nums, k, target, 0, 0, 0);
  }

  // k数之和
  public static int kSum(int[] nums, int k, int target, int start, int count, long sum) {
    if (k < 2) return count;

    if (k == 2) {
      return twoSum(nums, target, start, count, sum);
    }

    for (int i = start; i <= nums.length - k; i++) {
      // 剪枝
      if (nums[i] > 0 && sum + nums[i] > target) break;

      // 去重
      if (i > start && nums[i] == nums[i - 1]) continue;
      count = kSum(nums, k - 1, target, i + 1, count, sum + nums[i]);
    }

    return count;
  }

  // 两数之和
  public static int twoSum(int[] nums, int target, int start, int count, long preSum) {
    int l = start;
    int r = nums.length - 1;

    while (l < r) {
      long sum = preSum + nums[l] + nums[r];

      if (target < sum) {
        r--;
      } else if (target > sum) {
        l++;
      } else {
        count++;
        // 去重
        while (l + 1 < r && nums[l] == nums[l + 1]) l++;
        // 去重
        while (r - 1 > l && nums[r] == nums[r - 1]) r--;
        l++;
        r--;
      }
    }

    return count;
  }
}

Python算法源码

# 输入获取
nums = list(map(int, input().split()))
k = int(input())
target = int(input())


# 两数之和
def twoSum(nums, target, start, count, preTotal):
    l = start
    r = len(nums) - 1

    while l < r:
        total = preTotal + nums[l] + nums[r]

        if target < total:
            r -= 1
        elif target > total:
            l += 1
        else:
            count += 1
            # 去重
            while l + 1 < r and nums[l] == nums[l + 1]:
                l += 1
            # 去重
            while r - 1 > l and nums[r] == nums[r - 1]:
                r -= 1
            l += 1
            r -= 1

    return count


# k数之和
def kSum(nums, k, target, start, count, total):
    if k < 2:
        return count

    if k == 2:
        return twoSum(nums, target, start, count, total)

    for i in range(start, len(nums) - k + 1):
        # 剪枝
        if nums[i] > 0 and total + nums[i] > target:
            break

        # 去重
        if i > start and nums[i] == nums[i - 1]:
            continue
        count = kSum(nums, k - 1, target, i + 1, count, total + nums[i])

    return count


# 算法入口
def getResult():
    if k > len(nums):
        return 0

    nums.sort()
    return kSum(nums, k, target, 0, 0, 0)


# 算法调用
print(getResult())

C算法源码

#include <stdio.h>
#include <stdlib.h>

#define MAX_SIZE 200

int cmp(const void *a, const void *b) {
    return (*(int *) a) - (*(int *) b);
}

int getResult(int nums[], int nums_size, int k, int target);

int kSum(const int nums[], int nums_size, int k, int target, int start, int count, long sum);

int twoSum(const int nums[], int nums_size, int target, int start, int count, long preSum);

int main() {
    int nums[MAX_SIZE];
    int nums_size = 0;

    while (scanf("%d", &nums[nums_size++])) {
        if (getchar() != ' ') break;
    }

    int k;
    scanf("%d", &k);

    int target;
    scanf("%d", &target);

    printf("%dn", getResult(nums, nums_size, k, target));

    return 0;
}

int getResult(int nums[], int nums_size, int k, int target) {
    if (k > nums_size) return 0;

    qsort(nums, nums_size, sizeof(int), cmp);

    return kSum(nums, nums_size, k, target, 0, 0, 0);
}

// k数之和
int kSum(const int nums[], int nums_size, int k, int target, int start, int count, long sum) {
    if (k < 2) return count;

    if (k == 2) {
        return twoSum(nums, nums_size, target, start, count, sum);
    }

    for (int i = start; i <= nums_size - k; i++) {
        // 剪枝
        if (nums[i] > 0 && sum + nums[i] > target) break;

        // 去重
        if (i > start && nums[i] == nums[i - 1]) continue;
        count = kSum(nums, nums_size, k - 1, target, i + 1, count, sum + nums[i]);
    }

    return count;
}

// 两数之和
int twoSum(const int nums[], int nums_size, int target, int start, int count, long preSum) {
    int l = start;
    int r = nums_size - 1;

    while (l < r) {
        long sum = preSum + nums[l] + nums[r];

        if (target < sum) {
            r--;
        } else if (target > sum) {
            l++;
        } else {
            count++;

            // 去重
            while (l + 1 < r && nums[l] == nums[l + 1]) l++;
            // 去重
            while (r - 1 > l && nums[r] == nums[r - 1]) r--;

            l++;
            r--;
        }
    }

    return count;
}

题目解析（回溯算法+组合求解）

JS算法源码

const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;

void (async function () {
  const nums = (await readline()).split(" ").map(Number);
  const k = parseInt(await readline());
  const target = parseInt(await readline());

  let ans = 0;

  /**
   * 回溯算法 组合求解
   * @param {*} index 当前树层选取元素的起始位置，每次递归就是一层
   * @param {*} total 组合内元素之和
   * @param {*} count 组合内元素个数
   */
  function dfs(index, total, count) {
    // 组合内元素个数达到k个时
    if (count == k) {
      // 检查组合内元素之和是否为target
      if (total == target) {
        // 若是，则符合要求的元组个数+1
        ans++;
      }
      return;
    }

    for (let i = index; i < nums.length; i++) {
      // 树层去重
      if (i > index && nums[i] == nums[i - 1]) continue;
      // 回溯逻辑已隐含
      dfs(i + 1, total + nums[i], count + 1);
    }
  }

  nums.sort((a, b) => a - b);
  dfs(0, 0, 0);
  console.log(ans);
})();

Java算法源码

import java.util.Arrays;
import java.util.Scanner;

public class Main {
  static int[] nums;
  static int k;
  static int target;
  static int ans = 0;

  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);

    nums = Arrays.stream(sc.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();
    k = Integer.parseInt(sc.nextLine());
    target = Integer.parseInt(sc.nextLine());

    System.out.println(getResult());
  }

  public static int getResult() {
    Arrays.sort(nums);
    dfs(0, 0, 0);
    return ans;
  }

  /**
   * 回溯算法 组合求解
   *
   * @param index 当前树层选取元素的起始位置，每次递归就是一层
   * @param total 组合内元素之和
   * @param count 组合内元素个数
   */
  public static void dfs(int index, long total, int count) {
    // 组合内元素个数达到k个时
    if (count == k) {
      // 检查组合内元素之和是否为target
      if (total == target) {
        // 若是，则符合要求的元组个数+1
        ans += 1;
      }
      return;
    }

    for (int i = index; i < nums.length; i++) {
      // 树层去重
      if (i > index && nums[i] == nums[i - 1]) continue;
      // 回溯逻辑已隐含
      dfs(i + 1, total + nums[i], count + 1);
    }
  }
}

Python算法源码

nums = list(map(int, input().split()))
k = int(input())
target = int(input())

ans = 0


def dfs(index, total, count):
    """
    回溯算法 组合求解
    :param index: 当前树层选取元素的起始位置，每次递归就是一层
    :param total: 组合内元素之和
    :param count: 组合内元素个数
    """
    global ans

    # 组合内元素个数达到k个时
    if count == k:
        # 检查组合内元素之和是否为target
        if total == target:
            # 若是，则符合要求的元组个数+1
            ans += 1
        return

    for i in range(index, len(nums)):
        # 树层去重
        if i > index and nums[i] == nums[i - 1]:
            continue

        # 回溯逻辑已隐含
        dfs(i + 1, total + nums[i], count + 1)


def result():
    nums.sort()
    dfs(0, 0, 0)
    return ans


print(result())

C算法源码

#include <stdio.h>
#include <stdlib.h>

#define MAX_SIZE 200

int cmp(const void *a, const void *b) {
    return (*(int *) a) - (*(int *) b);
}
int getResult(int nums[], int nums_size, int k, int target);
void dfs(const int nums[], int nums_size, int k, int target, int index, long total, int count, int* ans);

int main() {
    int nums[MAX_SIZE];
    int nums_size = 0;

    while (scanf("%d", &nums[nums_size++])) {
        if (getchar() != ' ') break;
    }

    int k;
    scanf("%d", &k);

    int target;
    scanf("%d", &target);


    printf("%dn", getResult(nums, nums_size, k, target));

    return 0;
}

int getResult(int nums[], int nums_size, int k, int target) {
    int ans = 0;

    qsort(nums, nums_size, sizeof(int), cmp);
    dfs(nums, nums_size, k, target, 0, 0, 0, &ans);

    return ans;
}

void dfs(const int nums[], int nums_size, int k, int target, int index, long total, int count, int* ans) {
    // 组合内元素个数达到k个时
    if (count == k) {
        // 检查组合内元素之和是否为target
        if (total == target) {
            // 若是，则符合要求的元组个数+1
            (*ans)++;
        }

        return;
    }

    for (int i = index; i < nums_size; i++) {
        // 树层去重
        if (i > index && nums[i] == nums[i - 1]) {
            continue;
        }

        // 回溯
        dfs(nums, nums_size, k, target, i + 1, total + nums[i], count + 1, ans);
    }
}

免责声明：

1、IT资源小站为非营利性网站，全站所有资料仅供网友个人学习使用，禁止商用
2、本站所有文档、视频、书籍等资料均由网友分享，本站只负责收集不承担任何技术及版权问题
3、如本帖侵犯到任何版权问题，请立即告知本站，本站将及时予与删除下载链接并致以最深的歉意
4、本帖部分内容转载自其它媒体，但并不代表本站赞同其观点和对其真实性负责
5、一经注册为本站会员，一律视为同意网站规定，本站管理员及版主有权禁止违规用户
6、其他单位或个人使用、转载或引用本文时必须同时征得该帖子作者和IT资源小站的同意
7、IT资源小站管理员和版主有权不事先通知发贴者而删除本文

0

评论0

取消

首页 发现 VIP 我的

站点公告

没有账号？注册  忘记密码？