# LeetCode #151 Two Sum

Given an array of integers, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.

You may assume that each input would have exactly one solution.

Input: numbers={2, 7, 11, 15}, target=9

Output: index1=1, index2=2

代码：

#include 
    
     #include 
     
      #include 
      
       using namespace std;class Solution {public:    vector
       
         twoSum(vector
        
          &numbers, int target) {        vector
         
           temp = numbers; sort(temp.begin(), temp.end()); //cout<<*numbers.begin()<
          
           <
           
             target){ j--; }else{ i++; } for(int k = 0; k < temp.size(); k++){ if(numbers[k] == temp[i]) {index1 = k+1;break;} } for(int k = temp.size()-1; k >= 0; k--){ //cout<
            
             <
             
               index2){ int temp = index1; index1 = index2; index2 = temp; } vector
              
                result; result.push_back(index1); result.push_back(index2); return result; }};int main(){ //cout << "Hello world!" << endl; int nums[4] = {4,3,2,1}; vector
               
                 numbers(&nums[0], &nums[4]); Solution solution; vector
                
                  re = solution.twoSum(numbers, 5); cout<
                 
                  <<" "<
                 
                
               
              
             
            
           
          
         
        
       
      
     
    

总结：

• 一开始什么也没考虑写了个二重循环，结果时间超限
• 看了解析之后重写，结果忘记考虑 index1 < index2 WA了
• 之后又加了个判断才AC
• 时间复杂度O(nlogn) 还有个O(n)的解，要用map，以后写