两数之和

思路分析

给输入数组排序，然后两个指针，一个头指针，一个尾指针，一起往中间移动。如果两者的和小于target，头指针就向后移动；如果和大于target，尾指针就向前移动。直到找到和等于target的组合。
直接排序的话会丢了索引，这里特殊处理一下。

看到暴力解就能过，emmm这个就偏离初心了吧；主流的好像是HashMap解法，后面我也试试。

代码实现

带索引排序，用了下lambda表达式，学习新语法。写完在本地测试。

#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
vector<int> sortWithIndex(vector<int> &nums)
{
    vector<int> index(nums.size());
    for (int i = 0; i < index.size(); ++i)
    {
        index[i] = i;
    }
    sort(index.begin(), index.end(),
         [&nums](int a, int b) {
             return nums[a] < nums[b];
         });
    return index;
}
int main()
{
    vector<int> nums{4, 6, 3, 3, 5, 7};
    vector<int> index(nums.size());
    index = sortWithIndex(nums);
    for (vector<int>::iterator i = index.begin(); i != index.end(); ++i)
    {
        cout << *i << ":" << nums[*i] << endl;
    }
}

整体实现

class Solution {
private:
    vector<int> sortWithIndex(vector<int> &nums)
    {
        vector<int> index(nums.size());
        for (int i = 0; i < index.size(); ++i)
        {
            index[i] = i;
        }
        sort(index.begin(), index.end(),
            [&nums](int a, int b) {
                return nums[a] < nums[b];
            });
        return index;
    }
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> index(nums.size());
        // 排序后的索引值
        index = sortWithIndex(nums);
        int i = 0;
        int j = index.size() - 1;
        int sum;
        vector<int> ans;
        while (i < j){
            if (i==j){
                break;
            }
            sum = nums[index[i]] + nums[index[j]];
            if (sum == target){
                ans.emplace_back(index[i]);
                ans.emplace_back(index[j]);
                break;
            }
            else if (sum < target){
                i++;
            }
            else if (sum > target){
                j--;
            }
        }
        return ans;
    }
};