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

[songyy5517]

输入一个递增排序的数组和一个数字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]

分析 这道题本质上是在数组中找一堆数字满足其和等于s。由题可知，数组递增，因此可以考虑使用双指针。

[songyy5517]

思路：双指针

1. 异常处理；
2. 定义双指针分别指向数组的首尾；
3. 循环搜索，根据两指针的和更新指针位置；若和等于s，则返回两指针所指元素。

复杂度分析

• 时间复杂度： $O(N)$ ，双指针遍历数组的复杂度为 $O(N)$ ；
• 空间复杂度： $O(1)$ ，额外定义的双指针占用了常数大小的空间。

[songyy5517]

class Solution {
    public int[] twoSum(int[] nums, int target) {
        // 思路：双指针
        // 1. 异常处理
        if (nums == null || nums.length == 0)
            return null;

        // 2. 定义双指针
        int start = 0;
        int end = nums.length - 1;

        // 3. 循环搜索，根据两指针的元素之和更新指针
        while (start < end){
            int sum = nums[start] + nums[end];
            if (sum == target){
                return new int[]{nums[start], nums[end]};
            }
            else if (sum > target)
                end --;
            else
                start ++;
        }

        return new int[0];
    }
}

[songyy5517]

2023/11/24 2024/3/15 2024/3/21