题解 | #和为S的两个数字#
和为S的两个数字
http://www.nowcoder.com/practice/390da4f7a00f44bea7c2f3d19491311b
【问题描述】
- 在有序数组中找出两个数,使得和为给定的数 S。
- 如果有多对数字的和等于 S,输出两个数的乘积最小的。
【解题思路】
- 使用双指针,一个指针指向元素较小的值,一个指针指向元素较大的值。
- 指向较小元素值的指针,从头至尾遍历,指向较大元素的指针从尾到头遍历。
- 如果两个元素sum == target,则这两个元素即为所求;
- 如果这两个元素 sum < target,则移动较小元素,使得sum变大;
- 如果这两个元素 sum > target,则移动较大元素,使得sum变小;
【代码示例】
public ArrayList<Integer> finNumberWithSum(int[] nums, int target) { int i = 0, j = nums.length - 1; while (i < j) { int cur = nums[i] + nums[j]; if (cur == target) { return new ArrayList<>(Arrays.asList(nums[i], nums[j])); } if (cur < target) { i++; } else { j--; } } return new ArrayList<>(); }