twoSum

排序+左右双指针（假设有且只有一对元素可以凑出 target

vector<int> twoSum(vector<int>& nums, int target) {
    // 先对数组排序
    sort(nums.begin(), nums.end());
    // 左右指针
    int lo = 0, hi = nums.size() - 1;
    while (lo < hi) {
        int sum = nums[lo] + nums[hi];
        // 根据 sum 和 target 的比较，移动左右指针
        if (sum < target) {
            lo++;
        } else if (sum > target) {
            hi--;
        } else if (sum == target) {
            return {nums[lo], nums[hi]};
        }
    }
    return {};
}

更泛化：可能有多对元素之和等于 target 需返回所有元素对且不重复

要满足不重复，需在 if 各分支处操作 lo hi 指针跳过所有重复元素

vector<vector<int>> twoSumTarget(vector<int>& nums, int target) {
    // nums 数组必须有序
    sort(nums.begin(), nums.end());
    int lo = 0, hi = nums.size() - 1;
    vector<vector<int>> res;
    while (lo < hi) {
        int sum = nums[lo] + nums[hi];
        int left = nums[lo], right = nums[hi];
        if (sum < target) {
            while (lo < hi && nums[lo] == left) lo++;
        } else if (sum > target) {
            while (lo < hi && nums[hi] == right) hi--;
        } else {
            res.push_back({left, right});
            while (lo < hi && nums[lo] == left) lo++;
            while (lo < hi && nums[hi] == right) hi--;
        }
    }
    return res;
}

while 循环的时间复杂度 O(N) 排序的时间复杂度为 O(NlogN) 总的复杂度为 O(NlogN)

3Sum

复用 twoSum 函数

/* 从 nums[start] 开始，计算有序数组
 * nums 中所有和为 target 的二元组 */
vector<vector<int>> twoSumTarget(
    vector<int>& nums, int start, int target) {
    // 左指针改为从 start 开始，其他不变
    int lo = start, hi = nums.size() - 1;
    vector<vector<int>> res;
    while (lo < hi) {
        ...
    }
    return res;
}

vector<vector<int>> threeSumTarget(vector<int>& nums, int target) {
	sort(nums.begin(), nums.end());
	int n = nums.size();
	vector<vector<int>> res;
	for (int i = 0; i < n; i++) { // 穷举 threeSum 的第一个数
		vector<vector<int>> // 对 target-nums[i] 计算 twoSum
			tuples = twoSumTarget(nums, i+1, target-nums[i]);
	  // 如果存在满足条件的二元组，再加上 nums[i] 就是结果三元组
		for (vector<int>& tuple : tuples) {
			tuple.push_back(nums[i]);
			res.push_back(tuple);
		}
    // 跳过第一个数字重复的情况，否则会出现重复结果
		while(i < n - 1 && nums[i] == nums[i+1]) i++;
	}
	return res;
}