LeetCode 1. 两数之和【数组 + 哈希表】 C++ 和 Java版题解

男娘i 2021-07-25 01:45 258阅读 0赞

### [LeetCode 1. 两数之和][LeetCode 1.] ###

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

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。

示例:  
给定 nums = \[2, 7, 11, 15\], target = 9

因为 nums\[0\] + nums\[1\] = 2 + 7 = 9

所以返回 \[0, 1\]

##### C++代码 #####

朴素版，双重for循环，时间复杂度为O(n^2)

class Solution { 
    public:
        vector<int> twoSum(vector<int>& nums, int target)
        { 
        vector<int>res;
        for(int i=0;i<nums.size();i++)
        { 
            for(int j=0;j<i;j++)
            { 
                if(nums[i]+nums[j]==target)
                { 
                    res={ j,i};  //记录答案
                    break;
                }
            }
            if(res.size()>0) break;
        }    
        return res;
        }
    };

优化版  
使用 unordered< int,int>hash; 使用hash表进行优化，建立key(元素)到value(下标)的映射。时间复杂度为O(n)。

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

##### Java版 #####

class Solution 
    { 
        public int[] twoSum(int[] nums, int target) 
       { 
            HashMap< Integer,Integer>hash = new HashMap<Integer,Integer>();
            for(int i=0;i<nums.length;i++)
            { 
                int another =target-nums[i];
                if(hash.containsKey(another))    //查找key值
                { 
                    return new int[]{ hash.get(another),i};  //找到了直接返回
                }
                hash.put(nums[i],i);
            }
            return new int[]{ -1,-1};
        }
    }

关于unordered\_map的整理随后给出。

[LeetCode 1.]: https://leetcode-cn.com/problems/two-sum/