LeetCode problem 1 Two Sum

musicbear 2020-03-19 原文

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

先放代码：

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>

using namespace std;

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        int start = 0;
        int end = nums.size() - 1;
        vector<int> result;
        vector<size_t> idx(nums.size());
        iota(idx.begin(), idx.end(), 0);
        sort(idx.begin(), idx.end(), [&nums](size_t i1, size_t i2) {return nums[i1] < nums[i2]; });
        sort(nums.begin(), nums.end());
        int tmp = nums[start] + nums[end];
        while (tmp != target && start != end)
        {
            if (tmp > target)
            {
                end--;
            }
            else
            {
                start++;
            }
            tmp = nums[start] + nums[end];
        }
        if (start != end)
        {
            result.push_back(idx[start]);
            result.push_back(idx[end]);
        }
        return result;
    }
};

思路
1 暴力（未实现）
2 先排序，start+end和target相比较，大则end--，else start++，若找不到，start==end为结束条件

使用sort排序，没办法像Matlab那样返回排序的索引,搜到了如下解决方案

//vector<int>& nums
vector<size_t> idx(nums.size());
iota(idx.begin(), idx.end(), 0);
//用从起始值开始连续递增的值填充一个范围
sort(idx.begin(), idx.end(), [&nums](size_t i1, size_t i2) {return nums[i1] < nums[i2]; });
//lambda表达式为sort函数添加一个模式

后来看最快的大佬的代码加上了

ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);

试了一下，速度很快，找原因


还有很多人用了hash map，不过在本题中，只是单纯的使用一重循环+hash map和上面的代码时间差不多，空间消耗还更大

继续看大佬的代码，发现vector<pair<int, int>>的操作

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>

using namespace std;

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        std::ios::sync_with_stdio(false);
        cin.tie(0);
        int len = nums.size();
        vector<pair<int, int>> v_pair;
        for (int i = 0; i < len; i++)
        {
            v_pair.push_back({nums[i], i});
        }
        sort(v_pair.begin(), v_pair.end());
        int start = 0;
        int end = len - 1;
        int tmp = v_pair[start].first + v_pair[end].first;
        while (tmp != target)
        {
            if (tmp > target)
            {
                end--;
            }
            else
            {
                start++;
            }
            tmp = v_pair[start].first + v_pair[end].first;
        }
        vector<int> result;
        result.push_back(v_pair[start].second);
        result.push_back(v_pair[end].second);
        return result;
    }
};