数字之和

两数之和

给定一个整数的数组和一个目标值，在该数组中找出和为目标值的两个整数，并返回数字下标，数字不能重复使用。

vector<int> twoSum(vector<int>& nums, int target) { std::unordered_map<int, int> numap; for (int i = 0; i < nums.size(); i++) { auto iter = numap.find(target - nums[i]); if (iter != numap.end()) { return {iter->second, i}; } numap.insert(nums[i], i);//emplace 最大的作用是避免产生不必要的临时变量 //numap.emplace((nums[i], i)); } return {}; }

三数之和

给定一个长度为n的数组，判断数组中是否存在三个元素之和为0，找出满足条件且不重复的三元组。

哈希法：时间复杂度O(n^2)

vector<vector<int>> threeSum(vector<int>& nums) { vector<vector<int>> result; sort(nums.begin(), nums.end()); for (int i = 0; i < nums.size(); i++) { if (nums[i] > 0) continue; if (i > 0 && nums[i] == nums[i - 1]) continue; unordered_set<int> nuset; for (int j = i + 1; j < nums.size(); j++) { if (j > i+ 2 && nums[j] == nums[j - 1] && nums[j -1] == nums[j -2]) { continue; } int c = 0 - (nums[i] + nums[j]); if (nuset.find(c) != nuset.end()) { result.push_back({ nums[i], nums[j], c }); nuset.erase(nums[j]); } else { nuset.insert(nums[j]); } } } return result; }

双指针法：时间复杂度O(n^2)

需要两层循环，第一层循环i从下标0开始，同时定义一个left为i+1，right为数组末尾，三个数之和为0，即a+b+c=0；

a = nums[left] + nums[right]，如果三个数之和>0 ，right--，如果<0，left++，当left==right是结束

vector<vector<int>> threeSum(vector<int>& nums) { vector<vector<int>> result; sort(nums.begin(), nums.end()); for (int i = 0; i < nums.size(); i++) { if (nums[i] > 0) continue; if (i > 0 && nums[i] == nums[i - 1]) continue; int left = i + 1; int right = nums.size() - 1; while (right > left) { while (right > left && nums[right] == nums[right - 1]) right--; while (right > left && nums[left] == nums[left + 1]) left++; if (nums[i] + nums[left] + nums[right] > 0) right--; else if (nums[i] + nums[left] + nums[right] < 0) left++; else { result.push_back({ nums[i], nums[left], nums[right] }); //去重 while (right > left && nums[right] == nums[right - 1]) right--; while (right > left && nums[left] == nums[left + 1]) left++; right--; left++; } } } return result; }

四数之和

给定四个数组A，B，C，D，计算有多少个元组（i，j，k，l），是得A[i] + B[j] + C[k] + D[l] = 0

int fourSum(vector<int>& A, vector<int>& B, vector<int>& C,vector<int>& D) { unordered_map<int, int> numap; for (int a : A) { for (int b : B) { numap[a + b]++; } } int numCount = 0; for (int c : C) { for (int d : D) { if (numap.find(0 - (c + d)) != numap.end()) numCount += numap[0 - (c + d)]; } } return numCount; }