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

第一种方案是两重循环，时间复杂度为O(n^2)

 

public class Solution {     public int[] twoSum(int[] numbers, int target) {         // Start typing your Java solution below         // DO NOT write main() function                  //int index1 = 0;         //int index2 = 0;                  int[] results = new int[2];                  for(int i = 0; i < numbers.length - 1; i++){             for(int j = i + 1; j < numbers.length; j++){                 if(numbers[i] + numbers[j] == target){                     results[0] = i + 1;                     results[1] = j + 1;                     return results;                 }             }         }         return results;              } }

1 class Solution { 2 public: 3     vector
     
       twoSum(vector
      
        &numbers, int target) { 4         vector
       
        ::iterator first, second; 5         first = numbers.begin(); 6  7         vector
        
          indics; 8         for(;first < numbers.end() - 1; first ++) { 9             for(second = first + 1; second < numbers.end(); second ++) {10                 if(*first + *second == target) {11                     indics.push_back((first - numbers.begin()) + 1);12                     indics.push_back((second - numbers.begin()) + 1);13                 }14             }15         }        16         17         return indics;18     }19 };
        
       
      
     

 

第二种解决方法：hash 将所有元素都遍历一遍放入Map中，再扫描一遍即可 时间复杂度O(n)

1 class Solution { 2 public: 3     vector
     
       twoSum(vector
      
        &numbers, int target) { 4         // Start typing your C/C++ solution below 5         // DO NOT write int main() function 6         map
       
         mapping; 7         vector
        
          result; 8         for(int i = 0; i < numbers.size(); i++){ 9             mapping[numbers[i]] = i;10         }11 12         for(int i = 0; i < numbers.size(); i++){13             int searched = target - numbers[i];14             if(mapping.find(searched) != mapping.end()){15                 result.push_back(i + 1);16                 result.push_back(mapping[searched] + 1);17                 break;18             }19         }20         return result;21 22     }23 };
        
       
      
     

 

1 class Solution { 2 public: 3     vector
     
       twoSum(vector
      
        &numbers, int target) { 4         vector
       
        ::iterator first, second; 5         first = numbers.begin(); 6          7         map
        
          mapping; 8         for(;first < numbers.end(); first ++) { 9             mapping[*first] = (first - numbers.begin()) + 1;10         }11         12         map
         
          ::iterator it;13         vector
          
            indics;14 for(first = numbers.begin(); first < numbers.end(); first ++) {15 int remain = target - *first;16 it = mapping.find(remain);17 if(it != mapping.end() && (first - numbers.begin() + 1) != it->second) {18 indics.push_back(first - numbers.begin() + 1);19 indics.push_back(it->second);20 break;21 }22 }23 24 return indics;25 }26 };