| 167. 两数之和 II | 您所在的位置：网站首页 › 指针法输入数组 › 167. 两数之和 II |
167. 两数之和 II
|
给定一个已按照升序排列 的有序数组，找到两个数使得它们相加之和等于目标数。 函数应该返回这两个下标值 index1 和 index2，其中 index1 必须小于 index2。 说明: 返回的下标值（index1 和 index2）不是从零开始的。你可以假设每个输入只对应唯一的答案，而且你不可以重复使用相同的元素。示例: 输入: numbers = [2, 7, 11, 15], target = 9输出: [1,2]解释: 2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。
——题目难度:简单
分析 双指针解法(下图可说明)
——来源：力扣官方-代码如下 class Solution { public: vector twoSum(vector& numbers, int target) { int low = 0, high = numbers.size() - 1; while (low < high) { int sum = numbers[low] + numbers[high]; if (sum == target) { return {low + 1, high + 1}; } else if (sum > target) { high--; } else { low++; } } return {-1, -1}; } };
二分法 在数组中找到两个数，使得它们的和等于目标值，可以首先固定第一个数，然后寻找第二个数，第二个数等于目标值减去第一个数的差。利用数组的有序性质，可以通过二分查找的方法寻找第二个数。为了避免重复寻找，在寻找第二个数时，只在第一个数的右侧寻找。 ——来源：力扣官方-代码如下 class Solution { public: vector twoSum(vector& numbers, int target) { int n = numbers.size(); for(int i = 0; i < n; i++) { int left = i + 1, right = n - 1; /*进行二分查找*/ while (left target - numbers[i]) { right = mid - 1; } else { left = mid + 1; } } } return {-1, -1}; } };
|
【本文地址】
公司简介
联系我们
| 今日新闻 |
| 推荐新闻 |
| 专题文章 |