数组有序与查找关系

1. 两数之和

给定一个整数数组和一个目标值，找出数组中和为目标值的两个数。

你可以假设每个输入只对应一种答案，且同样的元素不能被重复利用。

示例:

给定 nums = [2, 7, 11, 15], target = 9因为 nums[0] + nums[1] = 2 + 7 = 9所以返回 [0, 1]

题目

解法一：暴力解法，复杂度o（n平方）

解法二，排序后，使用双索引对撞（参考letcode167 two sum ）

复杂度O（nlogn）+O(n)=O(nlogn)

解法3查找表。将所有元素放入查找表，之后对于每一个元素a，查找target-a是否存在

解法三

class Solution {

public:

    vector<int> twoSum(vector<int>& nums, int target) {

        unordered_map<int,int> record;

        for(int i=0;i<nums.size();i++)

        {

            int complement=target-nums[i];

            if(record.find(complement)!=record.end())

            {  int res[2]={i,record[complement]};

              return vector<int>(res,res+2);

        }

        record[nums[i]]=i;

    }

    throw invalid_argument("the input has no solution");

    }

};

时间复杂度O(N)空间复杂度O(N)；

类似题目15号3sum 18题4sum16题3sum closest