X数之和系列

两数之和

  vector<int> twoSum(vector<int> &nums, int target) {
    unordered_map<int, int> hash;
    // 遍历一次即可
    for (int i = 0; i < nums.size(); i++) {
      // t 就是第二个数
      int t = target - nums[i];
      auto it = hash.find(t);
      if (it != hash.end()) {
        // 找到的情况下，当前i是第二个数的位置了
        return {it->second, i};
      } else {  // 把第一个数填入到 hash 中
        hash[nums[i]] = i;
      }
    }
    return {};
  }

三数之和

vector<vector<int>> threeSum(vector<int> &nums) {
	vector<vector<int>> res;
	size_t n = nums.size();
	if (n < 3) return res;
	sort(nums.begin(), nums.end());
	
	// a:0 ~ n-2, b, c
	for (int i = 0; i < n - 2; ++i) {
	  if (i > 0 && nums[i] == nums[i - 1]) continue;
	
	  int a = nums[i];
	  int l = i + 1, r = n - 1;
	  while (l < r) {
	    int b = nums[l], c = nums[r];
	    if (a + b + c < 0) {
	      while (l < r && nums[l] == b) ++l;
	    } else if (a + b + c > 0) {
	      while (l < r && nums[r] == c) --r;
	    } else {
	      res.push_back({a, b, c});
	      while (l < r && nums[l] == b) ++l;
	      while (l < r && nums[r] == c) --r;
	    }
	  }
	}
	return res;
}

最接近的三数之和

int threeSumClosest(vector<int> &nums, int target) {
  int n = nums.size();
  if (n < 3) return 0;
  // 使用前三个数初始化
  int res = nums[0] + nums[1] + nums[2];
  // 先排序
  sort(nums.begin(), nums.end());
  // 双指针
  for (int i = 0; i < n - 2; ++i) {
    if (i > 0 && nums[i] == nums[i - 1]) continue;
    int a = nums[i];
    int l = i + 1, r = n - 1;
    while (l < r) {
      int b = nums[l], c = nums[r];
      int sum = a + b + c;
			// 更新最接近的数
      if (abs(target - sum) < abs(target - res)) {
        res = sum;
      }
			// 去重逻辑
      if (sum < target) {
        ++l;
        while (l < r && nums[l] == b) ++l;
      } else if (sum > target) {
        --r;
        while (l < r && nums[r] == c) --r;
      } else {
        return target;
      }
    }
  }
  return res;
}