题目

题目描述给出一个整数数组，请在数组中找出两个加起来等于目标值的数，你给出的函数twoSum 需要返回这两个数字的下标（index1，index2），需要满足 index1 小于index2.。注意：下标是从1开始的假设给出的数组中只存在唯一解例如：给出的数组为 {
   20, 70, 110, 150},目标值为90输出 index1=1, index2=2示例1输入[3,2,4],6返回值[2,3]

解析

暴力——o(n^2)

直接遍历所有可能暴力求解。

class Solution {
   public:    /**     *      * @param numbers int整型vector      * @param target int整型      * @return int整型vector     */    vector
   
     twoSum(vector
    
     & numbers, int target) {
           // write code here        int i=-1,j=-1;        for(i=0;i

哈希表——o(n)

降低时间复杂度，用空间换时间。

利用hash表存储number的位置，第二次遍历时，检查是否有numbers[i]对应的target-numbers[i]存在。

class Solution {
   public:    /**     *      * @param numbers int整型vector      * @param target int整型      * @return int整型vector     */    vector
   
     twoSum(vector
    
     & numbers, int target) {
           map
     
       imap;        for(int i=0;i
      
       0&&i!=imap[tmp]){
                   return {
   i+1,imap[tmp]+1};            }        }        return {
   -1,-1};    }};