前置知识

C++中map，有三种类型：

std::unordered_map 底层实现为哈希表，std::map 和std::multimap 的底层实现是红黑树。

454.四数相加 II

首先遍历nums1与nums2中不同数相加得到的值,并存入检查Map里面,Key为a+b的值,Value为出现的次数.

再遍历nums3与nums4,判断0 - (c + d)的值是否出现在检查Map中.

class Solution {
public:
  int fourSumCount(vector<int> &nums1, vector<int> &nums2, vector<int> &nums3,
                   vector<int> &nums4) {
    unordered_map<int, int> map;
    int count = 0;
    for (int a : nums1) {
      for (int b : nums2) {
        map[a + b]++;
      }
    }
    for (int c : nums3) {
      for (int d : nums4) {
        if (map.find(0 - (c + d)) != map.end()) {
          count += map[0 - (c + d)];
        }
      }
    }
    return count;
  }
};

388.赎金信

采用mutilset来解题

先用一次循环将magazine中出现的字母全部塞进multiset中

第二次循环再用foreach遍历ransomNote中的字母,如果find(c)不为end(),也就是如果在遍历到multiset的最后最后一个元素时都没有在multiset中找到c,那么就直接返回false,如果找到了c,就继续,设置一个迭代器it指向当前c的位置,然后用erase函数删除c(这样的好处是只删除一个匹配项).

注意这个语句

auto it = checkSet.find(c);
      checkSet.erase(it);//

这样的话每次只会删除mutilset中匹配的一个元素,如果用.erase(c)这种方式,会把set中的c全部删掉

class Solution {
public:
  bool canConstruct(string ransomNote, string magazine) {
    unordered_multiset<char> checkSet;
    for (char c : magazine) {
      checkSet.insert(c);
    }
    unordered_set<char>::iterator it = checkSet.begin();
    for (char c : ransomNote) {
      if (checkSet.find(c) == checkSet.end()) {
        return false;
      }
      auto it = checkSet.find(c);
      checkSet.erase(it);//
    }
    return true;
  }
};

15.三数之和

关于剪枝函数的选择,nums[i] == nums[i - 1]还是nums[i] == nums[i + 1]?
如果选择nums[i] == nums[i + 1]可能会导致直接跳过结果集,如
{-1, -1, 2}明明是结果集,但是会被直接跳过

class Solution {
public:
  vector<vector<int>> threeSum(vector<int> &nums) {
    int sum = 0;
    std::vector<std::vector<int>> res;
    std::sort(nums.begin(), nums.end());
    for (int i = 0; i < nums.size(); i++) {
      if (nums[i] > 0) {
        return res;
      }
      if (i > 0 && nums[i] == nums[i - 1]) { // 剪枝函数
        continue;
      }
      int left = i + 1;
      int right = nums.size() - 1;
      while (left < right) {
        sum = nums[i] + nums[left] + nums[right];
        if (sum > 0) {
          right--;
        } else if (sum < 0) {
          left++;
        } else {
          res.push_back(std::vector<int>{nums[i], nums[left], nums[right]});
          while (left < right && nums[left] == nums[left + 1]) {
            left++;
          }
          while (left < right && nums[right] == nums[right - 1]) {
            right--;
          }
          right--;
          left++;
        }
      }
    }
    return res;
  }
};

18.四数之和

如何理解二级剪枝?

for (int i = k + 1;i < nums.size(); i++) {
	        if (nums[k]+ nums[i] > target && nums[k]+nums[i]>=0) {}

我们将nums[k]+nums[i]看作一个整体,因为nums[k]+nums[i]>0成立,所以后一个数肯定为正数, nums[k]+nums[i]>target就可以进行剪枝操作,因为现在的容器内的数字是从小到大排序的,而且第二个数为正数,,如果前两个都大于target,后面再加只能更大.

一定要加nums[k]+nums[i]>0这个条件,因为如果是负数加负数,结果反而会变小,如果一开始前两数相加大于0,但由于后面的数是负数,再加上后面的数结果就又会变小,所以只判断nums[k]+nums[i]>target的话会出现错误

注意,这一句要用break,而不是直接return res,因为遍历i的时候,实际上外层还有一个循环,所以不能直接return

if (nums[k] + nums[i] > target && nums[k] + nums[i] >= 0) {
          break;
        }

嵌套循环中的break和continue都只对一层循环起作用，用在内层循环时，只对内层循环其作用，对外层循环无影响。

实现

class Solution {
public:
  vector<vector<int>> fourSum(vector<int> &nums, int target) {
    vector<vector<int>> res;
    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;
      }
      for (int i = k + 1; i < nums.size(); i++) {
        if (nums[k] + nums[i] > target && nums[k] + nums[i] >= 0) {
          break;
        }
        if (i > k + 1 && nums[i] == nums[i - 1]) {
          continue;
        }
        int left = i + 1;
        int right = nums.size() - 1;
        long sum = 0;
        while (left < right) {
          sum =(long) nums[k] + nums[i] + nums[left] + nums[right];
          if (sum > target) {
            right--;
          } else if (sum < target) {
            left++;
          } else {
            res.push_back(
                vector<int>{nums[k], nums[i], nums[left], nums[right]});
            while (left < right && nums[left] == nums[left + 1]) {
              left++;
            }
            while (left < right && nums[right] == nums[right - 1]) {
              right--;
            }
            right--;
            left++;
          }
        }
      }
    }
    return res;
  }
};