1. 两数之和

题目链接

解题思路：

• 方法一：两个for循环，时间复杂度：O(n^2)
• 方法二：先排序，然后双指针，时间复杂度：O(n * logn)
• 方法三：使用一个set，从左往右遍历，每次遍历到一个数num，先查找set，是否存在target - num的数，如果存在，直接返回了。时间复杂度：O(n)。
  • 因为题目需要下标，所以要用map，value就是下标。

方法三代码

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> preSum;    
        int n = nums.size();
        for (int i = 0; i < n; ++i) {
            if (preSum.count(target - nums[i]) != 0) {
                return {preSum[target - nums[i]], i};
            }
            preSum[nums[i]] = i;
        }
        return {-1, -1};
    }
};