两数之和

LeetCode-1-两数之和

分析

一个序列 - 头尾指针。

实现

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        int n = nums.size();
        typedef pair<int, int> PII;
        vector<PII> a;
        for (int i = 0; i < n; ++ i)
            a.push_back({ nums[i], i });
        sort(a.begin(), a.end());
        vector<int> res;
        for (int i = 0, j = n - 1; i < n; ++ i) {
            while (j > i && a[i].first + a[j].first > target) -- j;

            if (i != j && a[i].first + a[j].first == target) {
                res.push_back(min(a[i].second, a[j].second));
                res.push_back(max(a[i].second, a[j].second));
                break;
            }
        }
        return res;
    }
};