当前位置：首页 > article >正文

算法的学习笔记—和为 S 的两个数字(牛客JZ57)

article 2024/10/27 8:58:12

在这里插入图片描述

😀前言
在算法和数据结构中，寻找两个数字的和的问题十分常见，尤其在面试和实际开发中具有广泛的应用。今天，我们讨论一个具体的问题：在一个有序数组中找出和为给定数 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++;
    else
        j--;
}