1. Two Sum

题目

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.Example:Given nums = [2, 7, 11, 15], target = 9,Because nums[0] + nums[1] = 2 + 7 = 9,return [0, 1].

解析

class Solution_1 {public:    // O(n^2)    vector
    
      twoSum(vector
     
       &numbers, int target) {        vector
      
        vec;        if (numbers.size()==0)        {            return vec;        }        for (int i = 0; i < numbers.size()-1;i++)        {            for (int j = i + 1; j < numbers.size();j++)            {                if (numbers[i]+numbers[j]==target)                {                    vec.push_back(i);                    vec.push_back(j);                    break;                }            }        }        return vec;    }    // 使用一个哈希表(unorder_map)来解，第一遍扫描，保存到哈希表中，第二遍扫，看target-n在不在哈希表中，时间复杂度为O(n)。        // 元素有重复的时候multi??    vector
       
         twoSum(vector
        
          a, int target) {        int i, j, k, l, m, n;        map
         
          mymap; map
          
           ::iterator it; vector
           
            ans; for (i = 0; i < a.size(); i++){ it = mymap.find(target - a[i]); if (it != mymap.end()){ ans.push_back(it->second); ans.push_back(i); return ans; } else{ mymap.insert(make_pair(a[i], i)); } } } vector
            
              twoSum1(vector
             
              & nums, int target) { vector
              
                vec; if (nums.size()==0) { return vec; } sort(nums.begin(), nums.end()); int start = 0, end = nums.size()-1; while (start
              
             
            
           
          
         
        
       
      
     
    

题目来源