给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出 和为目标值 target 的那 两个 整数,并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是,数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。
暴力破解 O(n^2)
哈希表 2遍,1遍
第一次做力扣
编译错误:Char 1: error: control reaches end of non-void function [-Werror=return-type] [solution.c]
力扣的最后一行必须是return语句
第一反应就是这么写,暴力破解,没有弯弯绕绕
int* twoSum(int* nums, int numsSize, int target, int* returnSize){ int i,j; int *result=(int *)malloc(sizeof(int)*2); *returnSize=2; //returnSize是返回数组的大小,恒为2,不写报错 for(i=0;i<numsSize-1;i++) for(j=i+1;j<numsSize;j++) if(nums[i]+nums[j]==target){ result[0]=i; result[1]=j; return result; } return result; }
知识点:
(1)向量(vector)是一个能够存放任意类型的动态数组。采用的连续存储空间来存储元素,可以采用下标对vector的元素进行访问
(2)MapName[n[i]]=i;key重复的时候,更新value
(3)MapName.insert(),key重复的时候,保持value
括号里:
pair<int,string>(1,“aaa”)
make_pair(1,“aaa”)
map<int,string>::value_type(1,“aaa”)
(4)每个STL中的类都有value_type,为容器中盛装数据的类型
(5)::表作用域 a.类外引用静态成员函数或类外定义函数 b.命名空间作用域std::cout c. ::val表全局变量
将数组nums的值作为key,下标作为value存入map中
如果hash中存在与当前的num[i]和为target的key,且这个key的value不是他自身则找到了解
假设输入为[3,7,3,15],目标值为6。第一遍遍历,第二个3出现时,hash[3]的value由0更新为2。在第二遍遍历时,运行到i==0时,hash[3]的value为2表明了两个3不是同一个3,所以找到了解。
同理,不更新value值也一样。当解是两个相同值的数字a1,a2的时候,不更新value相当于存储下来的是a1的下标b1。运行到a1时为同一个数,不和要求继续运行。依次运行到a2,获得了a2丢失的下标,此时满足了不是同一个数的要求,得到答案。
class Solution { public: vector<int> twoSum(vector<int>& nums, int target) { map<int,int> hash; int n=nums.size(); for(int i=0;i<n;i++) hash[nums[i]]=i; for(int i=0;i<n;i++) if(hash.count(target-nums[i])==1&&hash[target-nums[i]]!=i) return {i,hash[target-nums[i]]}; return {}; } };
不可变类型:近似值传递
a=5 a=10 #5被丢弃重新生成a
可变类型:引用传递
a=[1,2,3] a[2]=5 #a不动,值修改
向字典dict插入键值对在判断语句后面,所以每个数字都是向它的前面找,且范围不包括他自身,所以无需再考虑解为2a,当前值为a的情况。
查找当前a2是否为解的一个的时候,此时{‘a2’:‘b2’}还没插进字典,不会损失掉数据a1的下标。
因为是从后往前找当前i必是第二个数字,不过题目对顺序没要求
class Solution: def twoSum(self, nums: List[int], target: int) -> List[int]: dict={} for i in range (0,len(nums)): if (target-nums[i]) in dict: return [dict[target-nums[i]],i] dict[nums[i]]=i
这是评论区的一个大哥的代码,我照着这个思路写了python的
数组拷贝(这里没用到)
1.clone,从object类继承来的。基本数据类型都可用,string类型值不变才可用。
2.System.arraycopy(a1,1,a2,3,3) (原数组,原开始位置,目标数组,目标开始位置,拷贝个数)
3.a2=Arrays.copyof(a1,3) (原数组,拷贝个数) 底层用的System.arraycopy
4.深度拷贝:实现Cloneable接口,并重写clone
class Solution { public int[] twoSum(int[] nums, int target) { // int[] a=nums.clone(); int[] indexs = new int[2]; HashMap<Integer,Integer> hash=new HashMap<Integer,Integer>(); for(int i = 0; i < nums.length; i++){ if(hash.containsKey(nums[i])){ indexs[0] = i; indexs[1] = hash.get(nums[i]); return indexs; } hash.put(target-nums[i],i); } return indexs; } }
第一道“简单”题就这么费劲,之前学的东西我真是一点不记得了ORZ