C++ 中未排序数组中与目标值最接近的对和

另一个传统的计算机算法问题是识别无序数组中两个值，它们的和最接近一个目标值。这个问题在各种不同的学科中都有很高的适用性。在许多不同的情况下，识别求和到特定值且最接近该值的组件可能至关重要，同时也非常具有挑战性，例如在推荐系统、金融分析或值近似、计算机中若干负载的分配中。这个主题特别有趣且有助于普遍理解各种计算方法，因为它结合了算法效率、搜索优化和正确计算需求的独特元素。

问题的概念特征是定义一个给定未排序整数数组中的两个不同分量，它们彼此以及与给定目标数字的接近程度尽可能高。正如所见，这个过程看起来相当直接，但其中包含大量的计算工作，尤其是在涉及大型数据集或数组未排序的情况下。复杂性 arises from the fact that since the array is unsorted and there is no one guiding the search, there is no shortcut, and every combination of the two elements must be checked. As such, a straightforward approach could quickly turn into a non-efficient one and thus call for the employment of more complicated methods to solve the problem under consideration within a fairly reasonable time.

问题本身基于接收一个未排序的整数数组并搜索两个不相交分量，它们的和尽可能接近目标数字的想法。以下看似一个直接的过程，但需要大量的计算工作，尤其是在处理大型数据集或数组未排序时。复杂性 arises from the fact that there is no organization within an unsorted array through which the search can be guided, so every pair of elements must be considered. For this reason, what initially may seem very simple could be rendered useless very quickly, requiring the use of superior methods to deal with the problem within a fairly reasonable amount of time.

因此，有必要寻找更好的算法，因为检查所有可能组合的直接方法相当耗时。蛮力方法非常方便且易于学习；然而，它无法处理大型数据集，因为时间复杂度为 O(n^2)。上述操作以二次时间运行，因为该方法单独考虑每个对，并且没有关于数组结构的额外知识。因此，对于大小为 n 的数组，该方法必须进行 n*(n - 1)/two 次比较，随着 n 的增加，这可能非常浪费。

但并非都是绝望的……通过使用各种更高级的技术，例如对给定数组进行排序，然后使用双指针方法，可以将复杂度降低到 O(n log n)，这比上述方法要好得多。排序元素的特性 enable faster lookup, notwithstanding the overhead caused by sorting the array to look for the nearest pair. When the array is sorted, the problem appears in a more approachable form, which is a two-pointer approach from the ends towards the middle to quickly find the good couple.

因此，本文将探讨旨在解决未排序数组中与目标最接近的对和问题的各种方法：优化方法和蛮力方法。我们将从评估和评估该技术目的的直接方法以及使用它的缺点开始。在下一部分，我们将探讨优化方法，该方法通过排序提供更好的结果，同时使用双指针策略。

本文旨在通过详细解释、代码序列和两种技术的基准测试，让读者了解处理此 C++ 问题的最佳方法。在指南结束时，读者将能够欣赏一种策略相对于另一种策略的具体优势，或者了解在什么情况下应该采用哪种策略。

理解方法

理解这些方法不仅可以扩展解决类似问题的技能集，还可以增加对算法如何构建和优化的知识——这些技能对任何计算机科学家或工程师都至关重要。

问题概要

事实上，我们的工作是完成一个经典的计算问题，该问题包括在一个随机排序的数组中找到两个整数，它们的和尽可能接近目标整数。这个问题看似简单，但提出了许多算法设计和优化问题，并且在许多情境下都很重要，例如金融和数据科学。

认识到问题

接下来面临的是背包问题，即在一个数字数组中，找出两个数字（至少）它们的和最接近一个称为目标的整数。这变得更糟，因为数组是未排序的，因此不提供任何可以习惯的特定序列。我们希望两个数字尽可能接近的数字就是目标值，这是一个整数值。

例如，考虑以下场景

Array [10, 22, 28, 29, 30, 40]

目标和 54

目标是找到数组中两个不同的元素，它们的和最接近 54。在这种情况下，最佳对是 (22, 30)，因为 22 + 30 = 52，这是数组中任何对能达到的最接近 54 的和。

这个问题为何重要？

这不仅仅是一个课堂练习：在课堂上，学习者扮演员工的角色，并通过实际场景进行工作。它在许多领域都有应用和现实世界的后果：它在许多领域都有应用和现实世界的后果

金融分析： 如果投资者管理投资组合，他/她可以寻找两个证券，这两个证券的价值之和最接近投资者希望投资组合达到的价值。因此，这些对可以根据当时的市场情况帮助做出最佳投资决策。

数据科学和机器学习： 在构建预测模型时，通常需要找到能够共同实现所需结果的特征和数据点的组合。类似地，对于这个问题：对中的一个值是特征或预测，另一个值是目标总和，代表了一个目标。

推荐系统： 电子商务和流媒体服务通常使用推荐算法来告知消费者产品或内容。通过了解哪两个项目最接近用户想要的内容，可以提高推荐的相关性；这将大大提高用户满意度，从而带来高使用率。

负载均衡： 在分布式环境中，公平分配多个服务器或处理器的计算负载非常重要。通过确定一组对，使得对中的两个作业在效率上最接近，可以实现均衡的负载分配。这反过来将提高系统功能，从而提高系统效率。

问题中的障碍

这个主题的第一个挑战是数组当前是无序的。如果我以某种索引方式组织给定的数组，那么用诸如二分查找或双指针方法之类的更简单的技术来解决问题就不会那么困难。然而，我们不能直接采用这些技术，尤其是在数组未排序的情况下。

如果可以使用蛮力技术来纠正这个问题，则可以考虑这一点。在这种情况下，将检查数组中的每个潜在对，计算它们的和，然后将和与给定的目标进行比较。

其中一些技术，尤其是蛮力方法，非常有用，特别是对于小型数据集；然而，鉴于大型数据集涉及大量的计算，它会变得很麻烦。这意味着随着数据量的增加，需要更有效的算法，这些算法可以在合理的时间内完成工作。

明确目标

考虑到难度和找到可行解决方案的重要性，目标是明确的：这意味着我们应该提出一种算法，该算法可以识别一个接近目标的数字对，但其运行时间应小于 O(n^2)。理想情况下，我们将找到一种在调用效率和读取准确性之间取得平衡，同时还能处理更大的数组而性能不会下降的方法。

在给定的未排序数组中，一组不同的元素与给定目标值的最接近和，实际上是问题陈述。由于数组的无序性，大多数算法的选择必须在一定的得失下进行考虑，并且必须做出选择以获得最准确的结果，同时牢记各自的计算时间。这个挑战与算法设计和优化人员相关，因为与一些仅仅是谜题的问题不同，这个问题在许多领域都有重大的现实世界影响。

蛮力方法的算法

蛮力算法的分步说明

初始化

• 首先初始化两个关键变量
• min_diff：此变量将跟踪任何对的和与目标之间的最小差值。它最初设置为一个非常大的值，例如 INT_MAX，以确保任何计算出的差值都会更小。
• closest_pair：此变量将存储和最接近目标的数字对。最初，它可以是空对或填充占位符值。

遍历所有可能的对

• 使用两个嵌套循环遍历数组并检查所有可能的元素对。外层循环选择对的第一个元素，内层循环选择第二个元素。
• 具体来说，让外层循环索引为 i（范围从 0 到 n-2），内层循环索引为 j（范围从 i+1 到 n-1）。这确保了每对都是唯一的，并避免将元素与自身进行比较。

计算每对的和

• 对于索引 (i, j) 的每个组合，计算元素 arr[i] 和 arr[j] 的和。此和表示当前考虑的对的组合值。

计算与目标的差值

• 通过计算绝对差值来确定此和与目标的接近程度：diff = abs(target - sum)。此步骤衡量对的和与目标的偏差程度。

如有必要，更新最接近的对

• 将计算出的差值 diff 与当前的 min_diff 进行比较。如果 diff 更小，则将 min_diff 更新为新的、更小的差值，并将 closest_pair 设置为当前对 (arr[i], arr[j])。此更新确保您始终跟踪提供最接近目标和的对。

继续直到所有对都被检查

嵌套循环继续迭代，直到检查完所有可能的对。在此过程结束时，变量 min_diff 和 closest_pair 将保存找到的最小差值和相应的数字对。

返回结果

检查完所有对后，算法将返回 closest_pair，其中包含和最接近目标的两个数字。

示例 1

输出

Pair closest to target 54 is (22, 30)

最优方法的算法

最优算法的详细描述

排列数组

• 将数组按非递减顺序排序是第一步。按从小到大的顺序排序对于正确使用双指针方法至关重要。排序数据需要 O(n log n) 时间。

设置第一个双指针

• 使用两个指针，一个左指针初始化为数组的开头（索引 0），另一个右指针初始化为数组的末尾（索引 n-1）。这些指针代表当前考虑的对的两个分量。

设置用于监控最接近对的变量

• min_diff 中应存储任意对的和与目标之间的最小差值，应将其设置为一个非常大的值（例如 INT_MAX）。
• 为了保存产生最接近目标总和的对，初始化一个 closest_pair 变量。当我们找到更好的配对时，它将被更新。

使用这两个提示重复

• 直到左指针小于右指针，进入一个持续的循环
• 确定总和：确定左指针和右指针处分量的总和：Arr[left] + Arr[Right] 等于总和。
• 验证差值：确定目标与此总和之间的精确差值：diff 等于 abs(sum - goal)。
• 重新访问最接近的对：如果 diff 小于 min_diff，则将 min_diff 更新为 diff，并将 closest_pair 设置为 (arr[left], arr[right])。

移动指针

• 如果总和小于所需金额，则左指针应向右移动一步 (left++)。这是因为通过将左指针移到更大的值来增加总和将导致更大的总和，这正是我们所需要的。
• 如果总和超过目标，则右指针向左移动一步 (right--)。这是因为将右指针移到较小的值会减小总和，这就是我们需要较小总和的原因。

关闭循环

当左指针不再小于右 指针时，循环终止。此时，已确定最接近的对，算法停止。

返回最接近的对

最后，返回 closest_pair，其中包含和最接近目标的两个数字。

示例 2

输出

Pair closest to target 54 is (22, 30)

方法效率比较

• 由于其 O(n^2) 的复杂度，蛮力方法仅适用于小型数组。
• 特别是对于大型数据集，复杂度为 O(n log n) 的优化方法具有更强的可扩展性。

效率与简洁性

• 蛮力方法是新手入门的绝佳起点，因为它易于使用和理解。
• 优化方法可产生明显更好的结果，但需要了解排序算法和双指针策略。

边界情况

两种方法都必须处理空数组、元素少于两个的数组或产生相同最接近和的多个对的数组等边界情况。应进一步检查这些情况。

空间复杂度

如果就地排序，则两种策略的额外空间复杂度为 O(1)。只有存储索引和最接近对的变量才会占用空间。

财务分析

通过识别最能近似期望投资组合价值的最有利投资对来最大化资产分配。

数据近似

选择组合效果最接近预期结果的两个数据点，以最小化数据拟合误差。

推荐系统

查找最能反映用户期望的两个项目对，可以在推荐系统中将其视为查找最接近目标的对和的任务。

负载均衡

将任务配对，使其总计算成本最接近目标数字，这是分布式计算中用于在服务器之间平衡负载的一种方法。

应用

深入了解各种应用可能有助于我们理解，尽管这个问题看起来很简单，但在现实生活中却可能产生重大影响。下面将讨论该算法在不同领域的一些最常见应用。

1. 投资组合增强和金融工作

在所有领域中，金融是该技术使用最多的领域，特别是在投资组合优化方面。

• 资产配对： 投资者在构建投资组合时会寻求实现一些财务目标，例如降低风险或获得特定回报。了解一种或多种资产（债券或股票）如何协同工作对投资者很有用。这使他们能够更有效地分配资源，并为投资组合带来最佳结果。当您希望通过结合高风险和高回报的投资与低风险的投资来实现特定利润水平并同时最小化波动性时，此方法很有帮助。
• 对冲策略： 因此，交易员可能被迫寻找波动性可以有效对冲的匹配资产对，以减少衍生品交易中的损失潜力。通过识别具有接近目标的组合，可以建立对冲来阻止由市场波动引起的可怕风险。

2. 机器学习和数据科学

评估相似性并搜索与目标值距离最近的项目对是数据科学和机器学习的许多应用中的关键任务。

• 特征工程是为给定的机器学习模型定义新特征的过程，其中给定的特征对（变量）接近目标。这是因为诸如回归模型之类的分析模型可以通过对因变量的两个特征求和来产生更准确的预测。
• 在处理大型数据集时，数据科学家可能会发现自己必须近似或抑制某些信息，但同时又要保留必要的数据。通过查找相加起来近似给定值的点对，可以清理数据，使数据集更简单，而不会显著影响数据的整体质量。这在处理“大数据”、进行分类或降低数据集维度时非常有用。

3. 深入研究在线购物和推荐引擎。

SOP 2 推荐算法对于提高流媒体服务和电子商务用户的参与度至关重要。

• 产品推荐： 显然，在使用在线购物中的推荐系统时，可以认为用户体验在识别用户最有可能购买哪些商品方面得到了显著改善。当您为下一次购买设定预算限制时，它可以帮助推荐总价接近用户预算的配饰。
• 内容策展： 像 Netflix 和 Spotify 这样的视频和音乐平台通常会尝试提供与用户偏好相关的内容。平台可以确定内容项（例如歌曲或电影）的配对，这些配对共同映射用户的听歌或观影习惯。这使得能够提供更具体、更具吸引力的内容选择，并提高用户满意度和用户保留率。

4. 医学研究与医疗保健

在最接近目标的对和问题中，这些方法与医疗保健和医学科学几乎所有重要领域都高度相关。

• 剂量优化： 在医疗治疗中，找出特定药物对，其组合效果最接近所需目标结果至关重要，尤其是在治疗涉及多种药物的情况下。例如，当患者接受化疗时，医生通常需要找到最有效且副作用最小的药物组合。理想的治疗计划是基于配对的聚合，使得它们最接近预期的治疗水平。
• 临床试验： 在某些情况下，在临床试验期间，科学家们致力于寻找生物标志物，其中两个变量的总和需要最接近期望的结果。这有助于理解不同方面如何相互关联，并有助于设计能产生所需治疗效果的临床试验。