先给题
给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出 和为目标值 的那 两个 整数,并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是,数组中同一个元素不能使用两遍。
你可以按任意顺序返回答案。
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/two-sum
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
首先我没考虑暴力破解,去想优良的解法,但一直找不到,后来试了一下暴力破解,其实暴力破解就是这答案的一种。
之所以记录这个简单的题是因为我没想到哈希,数据结构学了哈希却一直没用过,所以记录下这个题。
1.暴力破解
这个就不解释了,直接上代码。
1 vector<int> twoSum(vector<int>& nums, int target) { 2 for(int i = 0; i < nums.size() - 1; i++) 3 for(int j = i + 1; j < nums.size(); j++) 4 if(nums[i] + nums[j] == target) 5 return {i,j}; 6 return {}; 7 }
2.哈希
1 class Solution { 2 public: 3 vector<int> twoSum(vector<int>& nums, int target) { 4 unordered_map<int, int> hashtable; 5 for (int i = 0; i < nums.size(); ++i) { 6 auto it = hashtable.find(target - nums[i]); 7 if (it != hashtable.end()) { 8 return {it->second, i}; 9 } 10 hashtable[nums[i]] = i; 11 } 12 return {}; 13 } 14 };
来源于https://leetcode-cn.com/problems/two-sum/solution/liang-shu-zhi-he-by-leetcode-solution/
© 著作权归作者所有
举报
发表评论
0/200