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>>的操作，试了一下，感觉差不多
原文：https://www.cnblogs.com/musicbear/p/12527485.html