甘肃精神文明建设网站,wordpress 无法更新,wordpress 插件 原理,长春建站Day07 454.四数相加II383. 赎金信15. 三数之和18. 四数之和 454.四数相加II
题目链接#xff1a;454.四数相加II 寻找两个数组之和#xff0c;是否与另外两个数组之和有特定的关系。 因为数值可能跨度太大#xff0c;选择使用下标表示为对应的数值大小#xff0c;会很浪费… Day07 454.四数相加II383. 赎金信15. 三数之和18. 四数之和 454.四数相加II
题目链接454.四数相加II 寻找两个数组之和是否与另外两个数组之和有特定的关系。 因为数值可能跨度太大选择使用下标表示为对应的数值大小会很浪费内存空间。 target减去后两个数组之和的结果是否存在与前两个数组之和组成的集合中。又要返回满足题意的次数因此决定使用map而不是set。
class Solution {
public:int fourSumCount(vectorint nums1, vectorint nums2, vectorint nums3, vectorint nums4) {unordered_mapint, int map;for (auto i: nums1) {for (auto j: nums2) {map[i j];//nums1 nums2之和存入map}}int cnt 0;for (auto i: nums3) {for (auto j: nums4) {int target 0 - (i j);//查找target是否存在与map中if (map.find(target) ! map.end()) {cnt map[target];//target对应存在多少个都加入}}}return cnt;}
};383. 赎金信
题目链接383. 赎金信 判断ransomNote中的字符是否出现在magazine中。
class Solution {
public:bool canConstruct(string ransomNote, string magazine) {if (ransomNote.size() magazine.size()) {return false;}int record[z - A 1] {};//个数别查错了。1for (auto i : magazine) {record[i - A];}for (auto i : ransomNote) {record[i - A]--;//出现就直接返回不用在该循环之后再遍历recordif (record[i - A] 0) return false;}return true;}
};15. 三数之和
题目链接15. 三数之和 两个数之和第三个数与目标值运算之后是否出现在两个数之和中。 但是时间复杂度为 O ( n 2 ) O(n^2) O(n2)且要去重操作。 选择使用双指针注意去重操作。
class Solution {
public:vectorvectorint threeSum(vectorint nums) {vectorvectorint ret;sort(nums.begin(), nums.end());for (int i 0; i nums.size(); i) {if (nums[i] 0) break;//剪枝。没有不影响结果//i指针的去重if (i 0 nums[i] nums[i - 1]) continue;int left i 1, right nums.size() - 1;while (left right) {if (nums[i] nums[left] nums[right] 0) {right--;} else if (nums[i] nums[left] nums[right] 0) {left;} else {ret.push_back(vectorint{nums[i], nums[left], nums[right]});//left和right指针的去重。移动时注意满足边界条件while (left right nums[left] nums[left 1])left;while (left right nums[right] nums[right - 1])right--;left;right--;}}}return ret;}
};其中
while (left right nums[left] nums[left 1]) left;
while (left right nums[right] nums[right - 1]) right--;left;
right--;前两行和后两行顺序不能调换。 18. 四数之和
题目链接 18. 四数之和 三数之和再多套一个遍历。不用哈希理由三数之和。 注意剪枝条件不同于三数之和因为三数的target是0
class Solution {
public:vectorvectorint fourSum(vectorint nums, int target) {vectorvectorint ret;sort(nums.begin(), nums.end());//排序for (int k 0; k nums.size(); k) {if (nums[k] target nums[k] 0) break;//剪枝if (k 0 nums[k] nums[k - 1]) continue;//k去重for (int i k 1; i nums.size(); i) {if (nums[k] nums[i] target nums[k] nums[i] 0) break;//剪枝。ki是一个整体if (i k 1 nums[i] nums[i - 1]) continue;//i去重int left i 1, right nums.size() - 1;while (left right) {if ((long) nums[k] nums[i] nums[left] nums[right] target) right--;else if ((long) nums[k] nums[i] nums[left] nums[right] target) left;else {ret.push_back(vectorint{nums[k], nums[i], nums[left], nums[right]});while (left right nums[left] nums[left 1]) left;//left去重while (left right nums[right] nums[right - 1]) right--;//right去重right--;left;}}}}return ret;}
};if ((long) nums[k] nums[i] nums[left] nums[right] target)long是因为nums数组中的元素超过int范围导致溢出了。
