526互联

【leetcode】1.two sum

发布时间 2023-08-17 22:44:05作者: SharlynOUO

第一题给我干懵了...想达到这个要求把我脑壳都想痛了...Follow-up: Can you come up with an algorithm that is less than O(n2) time complexity?

一开始想过用map，但是不能解决重复key的问题。
然而我用sort，这个时间复杂度也不好确定。
假装我只用了O(n)！（搓手手）（溜走）xxx

class Solution {
public:
    
    
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<pair<int,int>> indexes;
        int len=nums.size();
        for(int i=0;i<len;i++){
            indexes.push_back(pair(nums[i],i));
        }
        

        sort(indexes.begin(),indexes.end());
        
        vector<int> result;
        int left=0,right=len-1;
        while(left<right){
            
            if(indexes[left].first+indexes[right].first==target){
                result.push_back(indexes[left].second);
                result.push_back(indexes[right].second);
                return result;
            }else if(indexes[left].first+indexes[right].first>target){
                right--;
            }else{
                left++;
            }
        }
        return result;
    }
};

贴一个做法。
这个思路：哈希表数和index，这个数进哈希表了key就按差值理解。每走过一个位置，在哈希表中找到对应的差值则返回{哈希表找到的差值index，当前位置}，找不到则当前位置进哈希表。
时间复杂度O(n)
空间复杂度O(n)

class Solution {
public:
    
    
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> idx; // 创建一个空哈希表
        for (int j = 0;; j++) { // 枚举 j
            // 在左边找 nums[i]，满足 nums[i]+nums[j]=target
            auto it = idx.find(target - nums[j]);
            if (it != idx.end()) // 找到了
                return {it->second, j}; // 返回两个数的下标
            idx[nums[j]] = j; // 保存 nums[j] 和 j
        }
    }
};

作者：灵茶山艾府
链接：https://leetcode.cn/problems/two-sum/solutions/2326193/dong-hua-cong-liang-shu-zhi-he-zhong-wo-0yvmj/

今日复习：
cpp中unorder_map和map的区别 和底层原理
sort简介