Two Sum
声明：博主为算法新手，博客仅作为个人学习记录
作为新手我的做法
（1）数组nums遍历一遍挑选出小于target的值及其下标，值存入temp,下标存到indices
（2）遍历temp找到符合temp[i]+temp[j]==target的两个值
（3）返回符合要求的两个数字的下标
#include <iostream>
#include <vector>class Solution {
public:std::vector<int> twoSum(std::vector<int>& nums, int target) {std::vector<int> indices={};std::vector<int> temp={};int j = 0;//先遍历一遍挑出小于target的值以及下标 nums=[2,7,11,15]for(size_t i = 0; i <= nums.size(); i++)if(nums[i] < target) {temp.push_back(nums[i]);//挑出值 temp=[2,7]indices.push_back(i);//记录下标 indices=[0,1]j++;}//遍历temp数组两两加和，如果等于target则返回下标for(size_t i=0; i < indices.size(); i++){for(size_t j=0; j < indices.size(); j++)if(temp[i] + temp[j] == target && i != j)return {indices[i], indices[j]};}// If no solution is found, return an empty vector or handle the error as neededreturn {};}
};
int main() {Solution s = Solution();std::vector<int> nums = {2,3,4,7,11,15};int target = 7;std::vector<int> result = s.twoSum(nums, target);if (!result.empty()) {std::cout << result[0] << " " << result[1] << std::endl;} else {std::cout << "No solution found" << std::endl;}return 0;
}
以上代码在一些情况下会出错：
例如：挑出操作中 nums[i] < target 会把–3挑出，而3没有被挑出来导致错误
Approach 1: Brute Force
直接遍历nums数组，外层确定一个数，内层循环找满足要求的另外一个数
#include <iostream>
#include <vector>class Solution {
public:std::vector<int> twoSum(std::vector<int>& nums, int target) {for(int i=0; i < nums.size(); i++){for(int j=i+1; j < nums.size(); j++)//为什么每次都从i+1处开始找?因为上一轮已经找过i和i以前的了且不满足条件if(nums[i] + nums[j] == target)return {i, j};}// If no solution is found, return an empty vector or handle the error as neededreturn {};}
};
大佬的其他解法
Approach 2: Two-pass Hash Table
（1）遍历nums数组并利用map容器同时保存数字及其下标
（2）遍历nums数组查找满足 target - nums[i] 的数字，根据map容器通过数字找到下标
（3）返回下标
#include <iostream>
#include <vector>
#include <unordered_map>
class Solution {
public:std::vector<int> twoSum(std::vector<int>& nums, int target) {//定义map容器std::unordered_map<int, int> temp;int n = nums.size();//遍历nums数组并利用map容器同时保存数字及其下标for (int i = 0; i < n; i++){temp[nums[i]] = i; //将 nums 数组中的第 i 个元素作为键（key），将 i 作为值（value）插入到 temp 这个 map 容器中}//遍历nums数组查找满足 target - nums[i] 的数字，根据map容器通过数字找到下标for (int i = 0; i < n; i++){int result = target - nums[i];//在map容器temp中查找是否有resultif (temp.count(result) && temp[result]!=i) //count函数如果找到值则返回1，否则返回0,要求找到的值其下标不能与减数一致{return {i,temp[result]};}}// If no solution is found, return an empty vector or handle the error as neededreturn {};}
};
int main() {Solution s = Solution();std::vector<int> nums = {-1,0,1,4,7,11,15};int target = 0;std::vector<int> result = s.twoSum(nums, target);if (!result.empty()) {std::cout << result[0] << " " << result[1] << std::endl;} else {std::cout << "No solution found" << std::endl;}return 0;
}
给map容器输入键值对的方式：
Approach 3: One-pass Hash Table
遍历nums的同时将遍历过的nums中的值插入到map容器中，方便后续在map容器中查找
#include <iostream>
#include <vector>
#include <unordered_map>
class Solution {
public:std::vector<int> twoSum(std::vector<int>& nums, int target) {std::unordered_map<int, int> temp;for(int i=0; i < nums.size(); i++){int complement = target - nums[i];//In C++, the find method of an unordered map searches for a key and returns an iterator to the element if it is found. //If the key is not found, it returns an iterator to the end of the map, which is represented by temp.end().if (temp.find(complement) != temp.end()) { //在temp中寻找已插入值nums数组中的complement值return {temp[complement], i};}temp[nums[i]] = i;}// If no solution is found, return an empty vector or handle the error as neededreturn {};}
};
int main() {Solution s = Solution();std::vector<int> nums = {0,4,-1,7,1,11,15};int target = 0;std::vector<int> result = s.twoSum(nums, target);if (!result.empty()) {std::cout << result[0] << " " << result[1] << std::endl;} else {std::cout << "No solution found" << std::endl;}return 0;
