LeetCode-15&16.三数之和

1. 三数之和

问题描述

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 _a + b + c = _0 ？请你找出所有满足条件且不重复的三元组。 注意：答案中不可以包含重复的三元组。 示例：

给定数组 nums = [-1, 0, 1, 2, -1, -4]，
满足要求的三元组集合为：
[
  [-1, 0, 1],
  [-1, -1, 2]
]

分析

先排序，然后使用2个index左右夹逼，另一个index在其中遍历查找符合需要的三元组。
时间复杂度

方法

vector<vector<int>> threeSum(vector<int>& nums) {
    vector<vector<int>> result;
    if(nums.size()<3){
        return result;
    }
    // 排序
    sort(nums.begin(),nums.end());

    const int target=0;
    auto last=nums.end();
    for(auto i=nums.begin();i<last-2;i++){
        auto j=i+1;
        if(i>nums.begin()&&*i==*(i-1)){
            continue;
        }
        auto k=last-1;
        while(j<k){
            // 三元组之和小于target，j++
            if(*i+*j+*k<target){
                j++;
                while(*j==*(j-1)&&j<k){
                    j++;
                }
            }else if(*i+*j+*k>target){    //三元组织和大于target
                k--;
                while(*k==*(k+1)&&j<k){
                    k--;
                }
            }else{
                // 符合要求的三元组
                result.push_back({*i,*j,*k});
                j++;
                k--;
                // 跳过重复元组
                while(*j==*(j-1)&&*k==*(k+1)&&j<k){
                    j++;
                    k--;
                }
            }
        }
    }
    return result;
}

2. 最接近的三数之和

问题描述

给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。 示例：

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

分析

首先对数组进行排序，然后在进行查询时固定一个最小元素，对数组中后续数字进行左右夹逼。
每次将当前组合的sum和target差的绝对值进行比较

• 差值变小时记录当前sum与gap

• 差值>min_gap,尝试调整组合

  • sum>target：c—，减小sum

  • sum

    方法

    int threeSumClosest(vector<int>& nums, int target) {
    int result = 0;
    int min_gap = INT_MAX;
    // 排序
    sort(nums.begin(), nums.end());
    
    for (auto a = nums.begin(); a != prev(nums.end(), 2); a++) {
       auto b = next(a);
       auto c = prev(nums.end());
       while (b < c) {
           const int sum = *a + *b + *c;
           const int gap = abs(sum - target);
           if (gap < min_gap) {
               result = sum;
               min_gap = gap;
           }
           if (sum < target) {
               b++;
           }
           else {
               c--;
           }
       }
    }
    return result;
    }