单页网站 开元,广州做网站多,天津 网站设计制作公司,企业营销型网站团队454. 四数相加 II
先用map记录前两个数的和num1 num2的值出现了多少次再在后两个数组里找0 - (num1 num2),找到后就累加map中的次数
class Solution {
public:int fourSumCount(vectorint nums1, vectorint nums2, vectorint nums3…454. 四数相加 II
先用map记录前两个数的和num1 num2的值出现了多少次再在后两个数组里找0 - (num1 num2),找到后就累加map中的次数
class Solution {
public:int fourSumCount(vectorint nums1, vectorint nums2, vectorint nums3,vectorint nums4) {unordered_mapint, int map;for (int num1 : nums1) {for (int num2 : nums2) {map[num1 num2];}}int count 0;for (int num3 : nums3) {for (int num4 : nums4) {int need 0 - (num3 num4);if (map.find(need) ! map.end()) {//这里是加上map[need]的次数不是countmap[need];}}}return count;}
};383. 赎金信
和242. 有效的字母异位词一样
class Solution {
public:bool canConstruct(string ransomNote, string magazine) {vectorint arr(26, 0);for (int i 0; i ransomNote.size(); i) {arr[ransomNote[i] - a];}for (int i 0; i magazine.size(); i) {arr[magazine[i] - a]--;}for (int n : arr) {if (n 0) {return false;}}return true;}
};15. 三数之和
首先对数组排序定义三个指针一个i从0开始遍历数组一个left在i右边一位,一个right在数组末尾确定i不断移动left和right同时要注意剪枝nums[i] 0第一个都大于0了那后面不管怎样也不可能等于0i 0 nums[i] nums[i - 1]重复元素就跳过要找前一个元素才是用过的元素找到三元数组收缩left和right时也需要去重,用while去找找到第一个不相等的元素
class Solution {
public:vectorvectorint threeSum(vectorint nums) {vectorvectorint ans;sort(nums.begin(), nums.end());for (int i 0; i nums.size(); i) {if (nums[i] 0) {return ans;}if (i 0 nums[i] nums[i - 1]) {continue;}int left i 1;int 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 {ans.push_back({nums[left], nums[right], nums[i]});while (left right nums[left] nums[left 1]) {left;}while (left right nums[right] nums[right - 1]) {right--;}left;right--;}}}return ans;}
};18. 四数之和
同上注意是和target做比较了数据太大需要加一个(long)
class Solution {
public:vectorvectorint fourSum(vectorint nums, int target) {vectorvectorint ans;sort(nums.begin(), nums.end());for (int i 0; i nums.size(); i) {if (nums[i] 0 nums[i] target) {return ans;}if (i 0 nums[i] nums[i - 1]) {continue;}for (int j i 1; j nums.size(); j) {if (nums[i] nums[j] target nums[i] nums[j] 0) {break;}if (j i 1 nums[j] nums[j - 1]) {continue;}int left j 1;int right nums.size() - 1;while (left right) {if ((long)nums[i] nums[j] nums[left] nums[right] target) {right--;} else if ((long)nums[i] nums[j] nums[left] nums[right] target) {left;} else {ans.push_back({nums[i], nums[j], nums[left], nums[right]});while (left right nums[left] nums[left 1]) {left;}while (left right nums[right] nums[right - 1]) {right--;}left;right--;}}}}return ans;}
};
