多数之和问题 | YOLOのBLOG

一、两数之和（简）

题目

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出和为目标值 target 的那两个整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。

示例 1：
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

示例 2：
输入：nums = [3,2,4], target = 6
输出：[1,2]

示例 3：
输入：nums = [3,3], target = 6
输出：[0,1]

提示：
2 <= nums.length <= 10^4
-10^9 <= nums[i] <= 10^9
-10^9 <= target <= 10^9
只会存在一个有效答案

题解

当我们需要查询一个元素是否出现过，或者一个元素是否在集合里的时候，就要第一时间想到哈希法。
数组可以做哈希表，set也可以，map也可以，用哪个呢
对于这道题，不仅要知道元素有没有遍历过，还有知道这个元素对应的下标。需要使用key-value结构来存放，key来存元素，value来存下标，那么使用map正合适
而C++中map有三种类型，如下所示:

映射	底层实现	是否有序	key的数量	能否更改数值	查询效率	增删效率
std::map	红黑树	key有序	只能有一个key	key不可修改	O(log n)	O(log n)
std::multimap	红黑树	key有序	可以有多个key	key不可修改	O(log n)	O(log n)
std::map	哈希表	key无序	只能有一个key	key不可修改	O(1)	O(1)

这道题目中并不需要key有序，所以选择std::unordered_map效率更高
接下来就很简单了，首先把数组中的元素作为key，value用来存下标；
我们只需要查找map中是否存在target-nums[i]的值，没有就将(nums[i],i)加入map，继续遍历即可

class Solution {
 public:
  vector<int> twoSum(vector<int>& nums, int target) {
    unordered_map<int, int> num_map;
    vector<int> res;
    for (int i = 0; i < nums.size(); i++) {
      auto iter = num_map.find(target - nums[i]);
      if (iter != num_map.end()) {
        res = {iter->second, i};
        break;
      }
      num_map.insert(pair<int, int>(nums[i], i));
    }
    return res;
  }
};

int main() {
  Solution s;
  vector<int> nums = {2, 7, 11, 15};
  int target = 22;
  vector<int> res = s.twoSum(nums, target);
  for (auto i : res) {
    cout << i << " ";
  }
}

二、三数之和（中）

题目

给你一个整数数组 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] 。
注意，输出的顺序和三元组的顺序并不重要。

示例 2：
输入：nums = [0,1,1]
输出：[]
解释：唯一可能的三元组和不为 0 。

示例 3：
输入：nums = [0,0,0]
输出：[[0,0,0]]
解释：唯一可能的三元组和为 0 。

提示：
3 <= nums.length <= 3000
-10^5 <= nums[i] <= 10^5

题解

这道题只用求值，不用求下标，就不需要用哈希表了，用双指针就是最方便的。
从小到大排序后，就可以用双指针了
因为有需要三个数，可以固定一个数a，双指针遍历剩下的数组，求双指针之和target为0-a即可
left为数组头，right为数组尾，大于target则right--，小于target则left++
主要是去重，因为有可能数组中同一个数字出现多次，排完序后，相同的数字会连在一起，只要将当前的值和前一个值比就可以去重了。

class Solution {
 public:
  vector<vector<int>> threeSum(vector<int>& nums) {
    vector<vector<int>> res;
    sort(nums.begin(), nums.end());
    // 目的是找出a + left + right = 0
    for (int i = 0; i < nums.size(); i++) {
      if (nums[i] > 0) {
        return res;
      }
      if (i > 0 && nums[i] == nums[i - 1]) {
        // 去重a
        continue;
      }
      int left = i + 1;
      int right = nums.size() - 1;
      int target = 0 - nums[i];
      while (left < right) {
        if (nums[left] + nums[right] > target) {
          right--;
        } else if (nums[left] + nums[right] < target) {
          left++;
        } else {
          res.push_back({nums[i], nums[left], nums[right]});
          // 找到答案时，双指针同时收缩
          left++;
          right--;
          while (left < right && nums[left] == nums[left - 1]) {
            // 去重left
            left++;
          }
          while (left < right && nums[right] == nums[right + 1]) {
            // 去重right
            right--;
          }
        }
      }
    }
  }
  return res;
};

三、最接近的三数之和（中）

题目

给你一个长度为 n 的整数数组 nums 和一个目标值 target。请你从 nums 中选出三个整数，使它们的和与 target 最接近。
返回这三个数的和。
假定每组输入只存在恰好一个解。

示例 1：
输入：nums = [-1,2,1,-4], target = 1
输出：2
解释：与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。

示例 2：
输入：nums = [0,0,0], target = 1
输出：0

提示：
3 <= nums.length <= 1000
-1000 <= nums[i] <= 1000
-10^4 <= target <= 10^4

题解

和三数之和非常类似，求与target最接近的三元组，即差值的绝对值最小。
和三数之和一样，从小到大排序后，固定一个数a，求双指针之和尽可能接近target-a即可
如果a+b+c>target，right--；如果a+b+c<target，left++，同时和三数之和一样需要去重，只是增加一步，在和taget比较之前，需要先update一下三数之和，记录下最接近target的值。

class Solution {
 public:
  int threeSumClosest(vector<int>& nums, int target) {
    int best = 1e7;
    // 根据差值的绝对值来更新答案
    auto update = [&](int cur) {
      // auto的特殊用法
      if (abs(cur - target) < abs(best - target)) {
        best = cur;
      }
    };

    sort(nums.begin(), nums.end());
    // 目的是找出a + left + right = 0
    for (int i = 0; i < nums.size(); i++) {
      if (i > 0 && nums[i] == nums[i - 1]) {
        // 去重a
        continue;
      }
      int left = i + 1;
      int right = nums.size() - 1;
      while (left < right) {
        int sum = nums[i] + nums[left] + nums[right];
        if (sum == target) {
          return target;
        }
        update(sum);
        if (sum > target) {
          right--;
          while (right > left && nums[right] == nums[right + 1]) {
            // 去重right
            right--;
          }
        } else {
          left++;
          while (right > left && nums[left] == nums[left - 1]) {
            // 去重left
            left++;
          }
        }
      }
    }
    return best;
  }
};