代码随想录 Day7
终极管理员 知识笔记 143阅读
提示文章写完后目录可以自动生成如何生成可参考右边的帮助文档
文章目录 今日学习目标一、算法题1.四数相加 II2.赎金信3.三数之和4.四数之和 学习及参考书籍
今日学习目标
四数相加 II454
赎金信383
三数之和15
四数之和18
题目
给你四个整数数组 nums1、nums2、nums3 和 nums4 数组长度都是 n 请你计算有多少个元组 (i, j, k, l) 能满足
0 < i, j, k, l < n
nums1[i] nums2[j] nums3[k] nums4[l] 0
示例 1
输入nums1 [1,2], nums2 [-2,-1], nums3 [-1,2], nums4 [0,2]
输出2
解释
两个元组如下
代码
class Solution {public: int fourSumCount(vector<int>& A, vector<int>& B, vector<int>& C, vector<int>& D) { unordered_map<int, int> umap; //key:ab的数值value:ab数值出现的次数 // 遍历大A和大B数组统计两个数组元素之和和出现的次数放到map中 for (int a : A) { for (int b : B) { umap[a b]; } } int count 0; // 统计abcd 0 出现的次数 // 在遍历大C和大D数组找到如果 0-(cd) 在map中出现过的话就把map中key对应的value也就是出现次数统计出来。 for (int c : C) { for (int d : D) { if (umap.find(0 - (c d)) ! umap.end()) { count umap[0 - (c d)]; } } } return count; }};题目
给你两个字符串ransomNote 和 magazine 判断 ransomNote 能不能由 magazine 里面的字符构成。
如果可以返回 true 否则返回 false 。
magazine 中的每个字符只能在 ransomNote 中使用一次。
示例 1
输入ransomNote “a”, magazine “b”
输出false
代码
class Solution {public: bool canConstruct(string ransomNote, string magazine) { int hash[26] {0}; if(ransomNote.size() > magazine.size()) { return false; } for(int i 0; i < magazine.length(); i) { hash[magazine[i] - a]; } for(int i 0; i < ransomNote.size(); i) { hash[ransomNote[i] - a]--; if(hash[ransomNote[i] - a] < 0) { return false; } } return true; }};题目
给你一个整数数组 nums 判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i ! j、i ! k 且 j ! k 同时还满足 nums[i] nums[j] nums[k] 0 。请
你返回所有和为 0 且不重复的三元组。
注意答案中不可以包含重复的三元组。
示例 1
输入nums [-1,0,1,2,-1,-4]
输出[[-1,-1,2],[-1,0,1]]
解释
nums[0] nums[1] nums[2] (-1) 0 1 0 。
nums[1] nums[2] nums[4] 0 1 (-1) 0 。
nums[0] nums[3] nums[4] (-1) 2 (-1) 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意输出的顺序和三元组的顺序并不重要。
代码
class Solution {public: vector<vector<int>> threeSum(vector<int>& nums) { vector<vector<int>> result; sort(nums.begin(), nums.end()); // 找出a b c 0 // a nums[i], b nums[j], c -(a b) for (int i 0; i < nums.size(); i) { // 排序之后如果第一个元素已经大于零那么不可能凑成三元组 if (nums[i] > 0) { break; } if (i > 0 && nums[i] nums[i - 1]) { //三元组元素a去重 continue; } unordered_set<int> set; for (int j i 1; j < nums.size(); j) { if (j > i 2 && nums[j] nums[j-1] && nums[j-1] nums[j-2]) { // 三元组元素b去重 continue; } int c 0 - (nums[i] nums[j]); if (set.find(c) ! set.end()) { result.push_back({nums[i], nums[j], c}); set.erase(c);// 三元组元素c去重 } else { set.insert(nums[j]); } } } return result; }};题目
给你一个由 n 个整数组成的数组 nums 和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] 若两个四元组元素一一对应则认为两个四元组重复
0 < a, b, c, d < n
a、b、c 和 d 互不相同
nums[a] nums[b] nums[c] nums[d] target
你可以按 任意顺序 返回答案 。
示例 1
输入nums [1,0,-1,0,-2,2], target 0
输出[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
代码
class Solution {public: vector<vector<int>> fourSum(vector<int>& nums, int target) { vector<vector<int>> result; sort(nums.begin(), nums.end()); for (int k 0; k < nums.size(); k) { // 剪枝处理 if (nums[k] > target && nums[k] > 0) { break; // 这里使用break统一通过最后的return返回 } // 对nums[k]去重 if (k > 0 && nums[k] nums[k - 1]) { continue; } for (int i k 1; i < nums.size(); i) { // 2级剪枝处理 if (nums[k] nums[i] > target && nums[k] nums[i] > 0) { break; } // 对nums[i]去重 if (i > k 1 && nums[i] nums[i - 1]) { continue; } int left i 1; int right nums.size() - 1; while (right > left) { // nums[k] nums[i] nums[left] nums[right] > target 会溢出 if ((long) nums[k] nums[i] nums[left] nums[right] > target) { right--; // nums[k] nums[i] nums[left] nums[right] < target 会溢出 } else if ((long) nums[k] nums[i] nums[left] nums[right] < target) { left; } else { result.push_back(vector<int>{nums[k], nums[i], nums[left], nums[right]}); // 对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; }};代码随想录