题目概要
在序列中找到和为特定值的两个元素的索引。
原题链接
解题思路
- 先将之排序
- 在排序之后的列表中查找符合条件的两个数
- 在原列表中找到这两个数的下标
复杂度分析
时间复杂度：$O(n)$
空间复杂度：$O(n)$
代码
class Solution {
public:
vector<int> twoSum(vector<int>& num, int target) {
// 1. 排序
std::vector<int> sorted = std::vector<int>(nums);
std::sort(sorted.begin(), sorted.end());
// 2. 查值
unsigned low = 0, high = sorted.size() - 1;
while (low < high) {
while (low < high && sorted[low] + sorted[high] < target) ++low;
while (low < high && sorted[low] + sorted[high] > target) --high;
if (sorted[low] + sorted[high] == target) break;
}
// 3. 查索引
std::vector<int> rvec;
int minIndex = -1, maxIndex = -1, sz = nums.size();
for (int i=0;i != sz;++i) {
if (minIndex == -1 && nums[i] == sorted[low]) minIndex = i;
else if (maxIndex == -1 && nums[i] == sorted[high]) maxIndex = i;
}
// 4. 给出答案
rvec.push_back(minIndex);
rvec.push_back(maxIndex);
return rvec;
}
};
广告区域
本人和小伙伴们承接各种软件项目，有需求的可以联系我们。
QQ: 2992073083
