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.

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

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

题目大意

给定一个数组，和一个目标值，从数组中找出两个和为目标值的数字，返回它们的编号

思路分析

step1：保存一个没排序的原始数组，方便后续找index（空间复杂度n），随后给数组排序（使用sort函数，时间复杂度为lg n） step2：对于已经排序的数组，从left 和 right 两个方向找数字，会出现四个情况：

恰好找到，这时候只需要按照值和步骤一保存的原始数组进行比对，找到index即可假设和大于目标值，那么–right，让和变小当和小于目标值，++left，让和变大

left 大于 right 的时候，结束

开销分析

时间复杂度 O(n） 空间复杂度 n

class Solution { public: vector<int> twoSum(vector<int>& nums, int target) { vector<int> copy_nums = nums; vector<int> sol; sort(nums.begin(),nums.end()); int left=0; int right =nums.size()-1; int sum=0; while(left <right) { sum = nums[left] +nums[right]; if( sum ==target) { for( int i=0;i<nums.size();++i) { if(copy_nums[i]==nums[left]) sol.push_back(i); else if(copy_nums[i]==nums[right]) sol.push_back(i); if(sol.size()==2) break; } return sol; } else if(sum<target) ++left; else --right; } } };