题目概要

在序列中找到和为特定值的两个元素的索引。

原题链接

LeetCode - Two Sum

解题思路

1. 先将之排序
2. 在排序之后的列表中查找符合条件的两个数
3. 在原列表中找到这两个数的下标

复杂度分析

时间复杂度：$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