和为s的两个数组-LeetCode57

发布于 — 2022 年 04 月 13 日
#LeetCode

题目描述

链接: https://leetcode-cn.com/problems/he-wei-sde-liang-ge-shu-zi-lcof/

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

解题思路

这个题目是LeetCode第一题两数之和类型, 都是从数组中找到两个数, 相加之和为s.

但是有区别的一点是, 这里的数组是已经升序排序好的. 所以我们可以利用升序的特性来进行优化.

双指针

我们将两个指针分别置为头尾, 然后判断这两个数之和与S的关系.

如果和大于S, 则尾指针向前移动一位

如果和小于S, 则头指针向后移动一位.

当和等于S时, 找到题解, 返回.

代码实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

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

相关题目

#LeetCode