😀前言
在算法和数据结构中，寻找两个数字的和的问题十分常见，尤其在面试和实际开发中具有广泛的应用。今天，我们讨论一个具体的问题：在一个有序数组中找出和为给定数 SSS 的两个数，并确保如果有多对数字满足要求，返回的数字乘积最小。
🏠个人主页：尘觉主页
文章目录
- 🥰和为 S 的两个数字
- 题目链接
- 😀题目解析
- 😃解题思路
- 😊代码解析
- 1. 初始化指针
- 2. 使用双指针进行查找
- 3. 返回结果
- 💖时间复杂度分析
- 🥳示例
- 😄总结
🥰和为 S 的两个数字
题目链接
牛客网
😀题目解析
在本题中，我们需要解决以下几个关键点：
- 找出数组中两个数，使它们的和等于给定的目标值 SSS。
- 如果存在多个满足条件的组合，返回乘积最小的那一对数字。
考虑到数组是有序的，我们可以利用双指针来高效地解决这个问题。
😃解题思路
由于数组有序，我们可以使用“双指针”方法。双指针是一种常用的算法优化技巧，可以将时间复杂度降低到 O(n)O(n)O(n)。解题步骤如下：
-
初始化两个指针：左指针
i指向数组的开头，右指针j指向数组的末尾。 -
求和判断
：
- 计算两个指针指向元素的和
cur = nums[i] + nums[j]。 - 如果
cur等于目标值S，我们找到了满足条件的两个数字，直接返回结果。 - 如果
cur小于S，说明需要更大的数，左指针i右移以增加总和。 - 如果
cur大于S，说明需要更小的数，右指针j左移以减小总和。
- 计算两个指针指向元素的和
-
循环终止：当左指针与右指针相遇时，说明没有找到符合条件的组合，返回空结果。
这种双指针的策略能够在保持高效性的同时保证结果的正确性。以下是代码实现：
public ArrayList<Integer> FindNumbersWithSum(int[] nums, int target) {// 初始化左指针 i 指向数组开头，右指针 j 指向数组末尾int i = 0, j = nums.length - 1;// 循环，当左指针小于右指针时继续查找while (i < j) {// 计算当前两个指针对应元素之和int cur = nums[i] + nums[j];// 如果当前和等于目标值，则找到了符合条件的两个数if (cur == target) {// 返回包含这两个数的列表return new ArrayList<>(Arrays.asList(nums[i], nums[j]));}// 如果当前和小于目标值，说明需要更大的数，移动左指针右移if (cur < target) {i++;} // 如果当前和大于目标值，说明需要更小的数，移动右指针左移else {j--;}}// 如果未找到符合条件的两个数，返回空列表return new ArrayList<>();
}😊代码解析
1. 初始化指针
代码的第一个步骤是初始化指针 i 和 j，分别指向数组的开头和结尾。
int i = 0, j = nums.length - 1;
2. 使用双指针进行查找
接下来进入循环。只要 i < j，我们就继续进行以下步骤：
- 求和判断：如果
nums[i] + nums[j]等于目标值target，则返回结果。 - 调整指针位置：如果当前和小于目标值，增加左指针；如果当前和大于目标值，减少右指针。
while (i < j) {int cur = nums[i] + nums[j];if (cur == target)return new ArrayList<>(Arrays.asList(nums[i], nums[j]));if (cur < target)i++;elsej--;
}3. 返回结果
如果找不到符合条件的两个数，返回一个空的列表。
return new ArrayList<>();
💖时间复杂度分析
因为双指针只需要遍历一次数组，所以算法的时间复杂度是 O(n)O(n)O(n)，其中 nnn 是数组的长度。这是该问题的最优复杂度，比暴力求解法（时间复杂度为 O(n2)O(n^2)O(n2)）高效得多。
🥳示例
以下是一个具体示例，帮助我们更好地理解代码运行过程：
int[] nums = {1, 2, 4, 7, 11, 15};
int target = 15;
假设我们使用上述数组和目标值 15：
- 初始化指针
i = 0和j = 5（指向1和15）。 nums[i] + nums[j] = 1 + 15 = 16，大于15，右指针左移。- 更新
j = 4（指向11），再次计算和：1 + 11 = 12，小于15，左指针右移。 - 更新
i = 1（指向2），再次计算和：2 + 11 = 13，小于15，左指针右移。 - 继续直到找到和为
15的组合[4, 11]，返回结果。
😄总结
使用双指针解题法有效地解决了有序数组中寻找和为给定值的问题。该方法不仅提高了算法的效率，还降低了时间复杂度，是面试中的常考题型。通过该题，我们学到了如何在有序数组中使用双指针高效查找满足特定条件的数对，提升了问题解决的能力。
😁热门专栏推荐
想学习vue的可以看看这个
java基础合集
数据库合集
redis合集
nginx合集
linux合集
手写机制
微服务组件
spring_尘觉
springMVC
mybits
等等等还有许多优秀的合集在主页等着大家的光顾感谢大家的支持
🤔欢迎大家加入我的社区 尘觉社区
文章到这里就结束了，如果有什么疑问的地方请指出，诸佬们一起来评论区一起讨论😁
希望能和诸佬们一起努力，今后我们一起观看感谢您的阅读🍻
如果帮助到您不妨3连支持一下，创造不易您们的支持是我的动力🤞
