leetcode 1. 两数之和

1. 两数之和

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

方法一：哈希

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> hashMap;
 
        for(int i = 0; i < nums.size(); ++i) {
            // 遍历当前元素，并在map中寻找是否有匹配的key
            if(hashMap.count(target - nums[i])) {
                return {hashMap[target-nums[i]], i};
            }
            /*
            auto iter = hashMap.find(target - nums[i]);
            if(iter != hashMap.end()) {
                return {iter->second, i};
            }
            */
            
            hashMap[nums[i]] = i;
            // hashMap.insert(pair<int, int>(nums[i], i)); 
        }
        return {};
    }
};

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

方法二：双指针

vector<int> twoSum(vector<int>& nums, int target) {
    // 先对数组排序
    sort(nums.begin(), nums.end());
    // 左右指针
    int left = 0, right = nums.size() - 1;
    while (left < right) {
        int sum = nums[left] + nums[right];
        // 根据 sum 和 target 的比较，移动左右指针
        if (sum < target) {
            left++;
        } else if (sum > target) {
            right--;
        } else if (sum == target) {
            return {nums[left], nums[right]};
        }
    }
    return {};
}

• 排序的时间复杂度是 O(n log n)，而双指针技术是 O(n)，因此算法的总体时间复杂度是 O(n log n)。
• 空间复杂度是 O(1)