侧边栏壁纸
博主头像
Lin2J博主等级

升级了服务器,访问应该会更加流畅🇨🇳

  • 累计撰写 94 篇文章
  • 累计创建 39 个标签
  • 累计收到 4 条评论

目 录CONTENT

文章目录

57 和为s的两个数字

Lin2J
2021-07-21 / 0 评论 / 0 点赞 / 151 阅读 / 713 字 / 正在检测是否收录...

剑指 Offer 57. 和为s的两个数字

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

解题思路:

因为给定的数组是有序的,这里可以用双指针来解题。

通过 $start$ 和 $end$ 指针,初始时 $start$ 指向第一个元素,$end$ 指向最后一个元素,两个元素不断向中间靠近。

靠近的过程中,判断两个指针指向的元素的和 $sum$ 是否为目标值 $target$:

  • 如果 $sum = target$,说明这两个数时符合要求的,返回 $start$ 和 $end$ 指向的元素;
  • 如果 $sum > target$,说明 $end$ 指向的数字太大,需要减小,$end$ 自减;
  • 如果 $sum < target$,说明 $start$ 指向的数字太小,需要增大,$start$ 自增。

代码:

public int[] twoSum(int[] nums, int target) {
    if (nums == null || nums.length < 2) {
        return new int[0];
    }
    int start = 0;
    int end = nums.length - 1;
    while (start < end) {
        if (nums[start] + nums[end] == target) {
            return new int[]{nums[start], nums[end]};
        } else if (nums[start] + nums[end] > target) {
            end--;
        } else {
            start++;
        }
    }
    return new int[0];
}

复杂度分析

  • 时间复杂度$O(N)$:最差情况下,需要遍历所有的元素。
  • 空间复杂度$O(1)$:辅助变量占用常数大小的额外空间。
0

评论区