长沙网站建设联系电话,怎么做表格,民政局网站建设工作总结,石景山区网站建设LeetCode Hot100 C 1.两数之和 给定一个整数数组 nums 和一个整数目标值 target#xff0c;请你在该数组中找出 和为目标值 target 的那 两个整数#xff0c;并返回它们的数组下标。 你可以假设每种输入只会对应一个答案#xff0c;并且你不能使用两次相同的元素。 你可以按…
LeetCode Hot100 C 1.两数之和 给定一个整数数组 nums 和一个整数目标值 target请你在该数组中找出 和为目标值 target 的那 两个整数并返回它们的数组下标。 你可以假设每种输入只会对应一个答案并且你不能使用两次相同的元素。 你可以按任意顺序返回答案 详情 给定一个整数数组 nums 和一个整数目标值 target请你在该数组中找出 和为目标值 target 的那 两个 整数并返回它们的数组下标。 你可以假设每种输入只会对应一个答案。但是数组中同一个元素在答案里不能重复出现。 你可以按任意顺序返回答案。 示例 1 输入nums [2,7,11,15], target 9 输出[0,1] 解释因为 nums[0] nums[1] 9 返回 [0, 1] 。 示例 2 输入nums [3,2,4], target 6 输出[1,2] 示例 3 输入nums [3,3], target 6 输出[0,1] 提示 2 nums.length 104 -109 nums[i] 109 -109 target 109 只会存在一个有效答案 进阶你可以想出一个时间复杂度小于 O(n2) 的算法吗 暴力循环
class Solution {
public:vectorint twoSum(vectorint nums, int target) {int nnums.size();for(int i0;in;i){for(int ji1;jn;j){if(nums[i]nums[j]target){return {i,j};}}}return {};}};哈希
可以使用单次循环来解决这个问题使用哈希记录已经出现过的数字 当循环到某一个数字就去哈希表查找是否有这个数字只需要一次循环
class Solution {
public:unordered_mapint,int hmap;vectorint twoSum(vectorint nums, int target) {for(int i0;inums.size();i){int subtarget-nums[i];if(hmap.count(sub)!0){//哈希表有数字则找到答案vectorint result{i,hmap[sub]};return result;}//没找到则继续把当前数字记录到哈希表中因为是要返回索引的hmap[nums[i]]i;} //为了编译顺利加一个返回 return vectorint(); }
};
unordered_mapint, int 类型它的赋值方式与传统数组有所不同它使用键值对来存储数据。在这里 hmap[nums[i]] i; 是一种典型的赋值方式
nums[i] 是键i 是值 hmap[nums[i]] i; 的意思是将 nums[i] 作为键将 i 作为与该键关联的值。如果键 nums[i] 已经存在于hmap中那么它对应的值将被更新为 i如果键 nums[i] 不存在unordered_map 会自动创建一个新的键值对。
