暴力法
2023.09.20 刚开始用暴力法破解（C++）
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
vector<int> a;
for(int i=0; i<nums.size()-1; i++) {
for(int j=i+1; j<nums.size(); j++) {
if(nums[i]+nums[j] == target) {
a.push_back(i);
a.push_back(j);
break;
}
}
}
return a;
}
};
哈希法
2023.12.22又做了一次（Java）
属于是只记得这题可以用哈希表快速解决，但是完全不知道怎么用、用在哪里，反而被困在这里了。
下面的代码，得到了错误答案
class Solution {
public int[] twoSum(int[] nums, int target) {
Map<Integer,Integer> mymap = new HashMap<>();
for(int i=0; i<nums.length; i++) {
mymap.put(nums[i],mymap.getOrDefault(nums[i],0));
}
int[] res = new int[2];
for(int i=0; i<nums.length; i++) {
int temp = target-nums[i];
if(mymap.containsKey(temp)) {
//K大写
res[0] = nums[i];
res[0] = temp;
break;
}
}
return res;
}
}
重新分析
首先审题，返回的是数组下标；
只存在一个有效答案=> 存在一个答案（不用考虑不存在答案的情况）
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。提示：
只会存在一个有效答案
这里出现一个问题，用 target-nums[i]在哈希表中查找很快，但是怎么构造哈希表，比如示例3数组为 nums = [3,3]，是无法构造以3为key值的两个pair的。所以肯定是边遍历边构造。
class Solution {
public int[] twoSum(int[] nums, int target) {
Map<Integer,Integer> mymap = new HashMap<>();
int[] res = new int[2];
for(int i=0; i<nums.length; i++) {
int temp = target-nums[i];
if(mymap.containsKey(temp)) {
//K大写
res[0] = i;
res[1] = mymap.get(temp);
break;
}
mymap.put(nums[i],i);
}
return res;
}
}
Java语法
Map<Integer, Integer> hashtable = new HashMap<Integer, Integer>();
containsKey ：K要大写
