題目概要

在序列中找到和為特定值的兩個元素的索引。

原題鏈接

LeetCode - Two Sum

解題思路

1. 先將之排序
2. 在排序之后的列表中查找符合條件的兩個數(shù)
3. 在原列表中找到這兩個數(shù)的下標(biāo)

復(fù)雜度分析

時間復(fù)雜度：$O(n)$
空間復(fù)雜度：$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;
    }
};

廣告區(qū)域

本人和小伙伴們承接各種軟件項(xiàng)目，有需求的可以聯(lián)系我們。
QQ: 2992073083