[每日一题] 第十四题:和为s的两个数字

题目描述

输入一个递增排序的数组和一个数字s,在数组中查找两个数,使得它们的和正好是s。如果有多对数字的和等于s,则输出任意一对即可。

示例 1:

输入:nums = [2,7,11,15], target = 9
输出:[2,7] 或者 [7,2]

示例 2:

输入:nums = [10,26,30,31,47,60], target = 40
输出:[10,30] 或者 [30,10]

限制:

  • 1 <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^6

题解

方法一:我的题解

因为是递增排序,我们就直接从数组两边遍历,定义一个 leftright,当两数之和小于 target时,说明要右移左边的数,当两数之和大于 target 时,说明要左移右边的数,当两数之和等于 target 时,输出结果。

注意:我的代码中没有判断如果不存在的情况,虽然通过了,但是是不对的,我没有改正,当做反例,下面的一个题解是正例。

代码

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int[] result = new int[2]; 
        int left = 0;
        int right = nums.length - 1;
        while ((nums[left] + nums[right]) != target) {
            if ((nums[left] + nums[right]) < target) {
                left ++;
            } else {
                right--;
            }
        }
        result[0] = nums[left];
        result[1] = nums[right];
        return result;
    }
}

复杂度分析

  • 时间复杂度: 需要遍历整个数组,所以时间复杂度为 O(N)。
  • 空间复杂度: 额外定义了两个变量 leftright,所以空间复杂度为 O(2)。

方法二:双指针法(和我的思路一致,更详细)

解题思路:

利用 HashMap 可以通过遍历数组找到数字组合,时间和空间复杂度均为 O(N);
注意本题的 nums 是 排序数组,因此可使用 双指针法 将空间复杂度降至 O(1)。

算法流程:

  1. 初始化: 双指针 i,j 分别指向数组 nums 的左右两端(俗称对撞双指针)。

  2. 循环搜索: 当双指针相遇时跳出:

    1. 计算和 s = nums[i] + nums[j];
    2. 若 s > target,则指针 j 向左移动,即执行 j = j - 1;
    3. 若 s < target,则指针 i 向右移动,即执行 i = i + 1;
    4. 若 s = target,立即返回数组 [nums[i], nums[j]];
  3. 返回空数组,代表无和为 target 的数字组合。

正确性证明:

记每个状态为 S(i,j) ,即 S(i,j)=nums[i]+nums[j] 。假设 S(i,j)<target ,则执行 i=i+1 ,即状态切换至 S(i+1,j) 。

  • 状态 S(i,j) 切换至 S(i+1,j) ,则会消去一行元素,相当于 消去了状态集合 {S(i,i+1),S(i,i+2),…,S(i,j−2),S(i,j−1),S(i,j) } 。(由于双指针都是向中间收缩,因此这些状态之后不可能再遇到)。
  • 由于 nums 是排序数组,因此这些 消去的状态 都一定满足 S(i,j)<target ,即这些状态都 不是解 。
  • 结论: 以上分析已证明 “每次指针 i 的移动操作,都不会导致解的丢失” ,即指针 i 的移动操作是 安全的 ;同理,对于指针 j 可得出同样推论;因此,此双指针法是正确的。

[每日一题] 第十四题:和为s的两个数字

代码

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int i = 0, j = nums.length - 1;
        while(i < j) {
            int s = nums[i] + nums[j];
            if(s < target) i++;
            else if(s > target) j--;
            else return new int[] { nums[i], nums[j] };
        }
        return new int[0];
    }
}

复杂度分析

  • 时间复杂度 O(N) : N 为数组 nums 的长度;双指针共同线性遍历整个数组。
  • 空间复杂度 O(1) : 变量 i, j 使用常数大小的额外空间。

题解来源

作者:jyd
链接:leetcode-cn.com/problems/he-wei-sd...
来源:力扣(LeetCode)

来源

来源:力扣(LeetCode)
链接:leetcode-cn.com/problems/he-wei-sd...

本作品采用《CC 协议》,转载必须注明作者和本文链接
讨论数量: 0
(= ̄ω ̄=)··· 暂无内容!

请勿发布不友善或者负能量的内容。与人为善,比聪明更重要!