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

太过爱你忘了你带给我的痛 2022-12-19 08:49 190阅读 0赞

# 题目 #

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

来源：力扣（LeetCode）  
链接：[https://leetcode-cn.com/problems/he-wei-sde-liang-ge-shu-zi-lcof][https_leetcode-cn.com_problems_he-wei-sde-liang-ge-shu-zi-lcof]

# 解题思路 #

递增排序数组: 想到二分法和双指针

本题使用双指针来解决

*  定义左右指针left,right
 *  计算nums\[left\] + nums\[right\]的值和target的关系
    
     *  等于,直接返回
     *  大于,右指针左移
     *  小于,左指针右移

# 代码 #

class Solution { 
    
        public int[] twoSum(int[] nums, int target) { 
            int[] resultArray = new int[0];
            if (nums == null || nums.length <= 1) { 
                return resultArray;
            }
    
            // 数组有序,使用双指针
            int left = 0;
            int right = nums.length - 1;
            while (left <= right) { 
                // 求和
                int sum = nums[left] + nums[right];
                if (sum > target) { 
                    // 大于目标值, 右指针左移
                    right--;
                } else if (sum < target) { 
                    // 小于目标值, 左指针右移
                    left++;
                } else { 
                    // 等于目标值
                    return new int[]{ nums[left], nums[right]};
                }
            }
    
            return resultArray;
        }
    
    }

# 复杂度 #

*  时间复杂度:O(n),最差情况下,数组全部遍历一遍
 *  空间复杂度:O(1),常数级额外空间

[https_leetcode-cn.com_problems_he-wei-sde-liang-ge-shu-zi-lcof]: https://leetcode-cn.com/problems/he-wei-sde-liang-ge-shu-zi-lcof