15/16-三数之和

LeetCode 15. 3Sum

LeetCode-15

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.

Notice that the solution set must not contain duplicate triplets.

Example 1:

Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]

题意解析

找到三个数和为0，不能重复使用同一个元素，也不能有相同的结果

method: 双指针

其实有三个指针，i, l, r，i负责遍历数组，l到r维护区间[i+1, end)
注意去重

时间复杂度：$O(n^2)$

• 剪枝：因为是从小到大排序，如果第一个nums[i]大于0，后面肯定都大于0，所以直接返回

• 去重：因为已经排好序了，如果元素相同，指针就一直往后或往前移

vector<vector<int>> threeSum(vector<int>& nums) {
    vector<vector<int>> ret;
    sort(nums.begin(), nums.end()); // 排序
    for (int i = 0; i < nums.size(); ++i) {
        if (nums[i] > 0) return ret;    // 剪枝
        if (i > 0 && nums[i] == nums[i - 1]) continue;  // i的去重
        int l = i + 1;
        int r = nums.size() - 1;
        while (l < r) {
            if (nums[i] + nums[l] + nums[r] > 0) r--;
            else if (nums[i] + nums[l] + nums[r] < 0) l++;
            else {
                ret.push_back(vector<int>{nums[i], nums[l], nums[r]});
                while (l < r && nums[l] == nums[l + 1]) l++;
                while (l < r && nums[r] == nums[r - 1]) r--;
                l++;    // 还要再移一格
                r--;
            }
        }
    }
    return ret;
}

---

LeetCode 16. 3Sum Closest

LeetCode-16

Given an integer array nums of length n and an integer target, find three integers in nums such that the sum is closest to target.

Return the sum of the three integers.

You may assume that each input would have exactly one solution.

Example 1:

Input: nums = [-1,2,1,-4], target = 1
Output: 2
Explanation: The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

method: 三指针

不一定等于target，找最接近的

跟三数之和一样的三个指针，如果三数和与target的差值比diff小，就更新diff，记录结果

int diff = INT_MAX;
int res;
int threeSumClosest(vector<int>& nums, int target) {
    sort(nums.begin(), nums.end());
    for (int i = 0; i < nums.size(); i++) {
        int l = i + 1;
        int r = nums.size() - 1;
        while (l < r) {
            int sum = nums[i] + nums[l] + nums[r];
            if (abs(sum - target) < diff) { // 差值更小就更新
                diff = abs(sum - target);
                res = sum;
            }
            if (sum > target) r--;
            else l++;   // 不断缩小范围
        }
    }
    return res;
}