【题目】

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

【分析】

类似于

【代码】

/**********************************   日期：2015-01-15*   作者：SJF0115*   题目: 1.Two Sum*   网址：https://oj.leetcode.com/problems/two-sum/*   结果：AC*   来源：LeetCode*   博客：**********************************/#include 
    
     #include 
     
      #include 
      
       using namespace std;class Solution {public:    vector
       
         twoSum(vector
        
          &numbers, int target) {        vector
         
           result; vector
          
            num = numbers; int count = numbers.size(); if(numbers.empty()){ return result; }//if // 排序 sort(numbers.begin(),numbers.end()); // 二分查找变形 for(int i = 0,j = count-1;i < j;){ int sum = numbers[i] + numbers[j]; // 找到目标 if(sum == target){ return FindIndex(num,numbers[i],numbers[j]); } // 当前和大于目标,需要变小一些 else if(sum > target){ j--; } // 当前和小于目标,需要变大一些 else{ i++; } }//for return result; }private: // 寻找下标 vector
           
             FindIndex(vector
            
              &numbers,int num1,int num2){ int count = numbers.size(); vector
             
               result; int index1,index2; bool flag1 = false,flag2 = false; for(int i = 0;i < count;++i){ if(flag1 == false && numbers[i] == num1){ index1 = i+1; flag1 = true; } else if(flag2 == false && numbers[i] == num2){ index2 = i+1; flag2 = true; } }//for // 交换 使index1 < index2 if(index1 > index2){ int tmp = index1; index1 = index2; index2 = tmp; }//if result.push_back(index1); result.push_back(index2); return result; }};int main(){ Solution solution; vector
              
                num; num.push_back(0); num.push_back(4); num.push_back(3); num.push_back(0); //num.push_back(15); int target = 0; // 查找 vector
               
                 vec = solution.twoSum(num,target); // 输出 cout<<"Index1->"<
                
                 <<" Index2->"<
                 
                  <