寒假刷题Day18

一、16. 最接近的三数之和

这一题有负数，没有单调性，不能“大了右指针左移，小了左指针右移，最后存值域求差绝对值”。

class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
        ranges::sort(nums);
        int ans, n = nums.size();
        int min_diff = INT_MAX;
        for (int i = 0; i < n - 2; i++) {
            int x = nums[i];
            if (i > 0 && x == nums[i - 1]) {
                continue; // 优化三
            }

            // 优化一
            int s = x + nums[i + 1] + nums[i + 2];
            if (s > target) { // 后面无论怎么选，选出的三个数的和不会比 s 还小
                if (s - target < min_diff) {
                    ans = s; // 由于下面直接 break，这里无需更新 min_diff
                }
                break;
            }

            // 优化二
            s = x + nums[n - 2] + nums[n - 1];
            if (s < target) { // x 加上后面任意两个数都不超过 s，所以下面的双指针就不需要跑了
                if (target - s < min_diff) {
                    min_diff = target - s;
                    ans = s;
                }
                continue;
            }

            // 双指针
            int j = i + 1, k = n - 1;
            while (j < k) {
                s = x + nums[j] + nums[k];
                if (s == target) {
                    return target;
                }
                if (s > target) {
                    if (s - target < min_diff) { // s 与 target 更近
                        min_diff = s - target;
                        ans = s;
                    }
                    k--;
                } else { // s < target
                    if (target - s < min_diff) { // s 与 target 更近
                        min_diff = target - s;
                        ans = s;
                    }
                    j++;
                }
            }
        }
        return ans;
    }
};

二、611. 有效三角形的个数

由示例可知，需要去重

class Solution {
public:
    int triangleNumber(vector<int>& nums) {
        ranges::sort(nums);
        int ans = 0;
        for (int k = 2; k < nums.size(); k++) {
            int c = nums[k];
            int i = 0; // a=nums[i]
            int j = k - 1; // b=nums[j]
            while (i < j) {
                if (nums[i] + nums[j] > c) {
                    // 由于 nums 已经从小到大排序
                    // nums[i]+nums[j] > c 同时意味着：
                    // nums[i+1]+nums[j] > c
                    // nums[i+2]+nums[j] > c
                    // ...
                    // nums[j-1]+nums[j] > c
                    // 从 i 到 j-1 一共 j-i 个
                    ans += j - i;
                    j--;
                } else {
                    // 由于 nums 已经从小到大排序
                    // nums[i]+nums[j] <= c 同时意味着
                    // nums[i]+nums[j-1] <= c
                    // ...
                    // nums[i]+nums[i+1] <= c
                    // 所以在后续的内层循环中，nums[i] 不可能作为三角形的边长，没有用了
                    i++;
                }
            }
        }
        return ans;
    }
};

优化：
1.如果发现最小的 a 和 b 相加大于 c，直接加入(k+1)k(k−1) / 6​ 为答案

2.发现最大的 a 和 b 相加小于等于 c，逃过此次内循环

class Solution {
public:
    int triangleNumber(vector<int>& nums) {
        ranges::sort(nums);
        int ans = 0;
        for (int k = nums.size() - 1; k > 1; k--) {
            int c = nums[k];
            if (nums[0] + nums[1] > c) { // 优化一
                ans += (k + 1) * k * (k - 1) / 6;
                break;
            }
            if (nums[k - 2] + nums[k - 1] <= c) { // 优化二
                continue;
            }
            int i = 0; // a=nums[i]
            int j = k - 1; // b=nums[j]
            while (i < j) {
                if (nums[i] + nums[j] > c) {
                    ans += j - i;
                    j--;
                } else {
                    i++;
                }
            }
        }
        return ans;
    }
};

三、1577. 数的平方等于两数乘积的方法数

1.哈希
开两个map分别存两个数组的平方，然后对于每个数组去n^2枚举，看在另一个数组的map存值里有多少个加起来就好。

class Solution {
public:
    #define ll long long 
    map<ll,int> mp1,mp2;
    int numTriplets(vector<int>& nums1, vector<int>& nums2) {
        for(auto it:nums1) mp1[1ll*it*it]++;
        for(auto it:nums2) mp2[1ll*it*it]++;
        ll ans=0;
        for(int i=0;i<nums1.size();i++){
            for(int j=i+1;j<nums1.size();j++){
                ans+=mp2[1ll*nums1[i]*nums1[j]];
            }
        }
        for(int i=0;i<nums2.size();i++){
            for(int j=i+1;j<nums2.size();j++){
                ans+=mp1[1ll*nums2[i]*nums2[j]];
            }
        }
        return ans;
    }
};

2.双指针

注意有相同的数字满足时，要左右相乘

class Solution {
    int s;
public:
    int numTriplets(vector<int>& nums1, vector<int>& nums2) {
        s = 0;
        process(nums1, nums2);
        process(nums2, nums1);
        return s;
    }
    void process(vector<int>& nums1, vector<int>& nums2) 
    {
        long long n1 = nums1.size(), n2 = nums2.size(), t1, t2, i, j, k;
        sort(nums2.begin(), nums2.end());//后者排序
        for(i = 0; i < n1; i++)
        {
            j = 0, k = n2-1;//双指针
            t1 = (long long)nums1[i]*nums1[i];
            while(j < k)
            {
                t2 = (long long)nums2[j]*nums2[k];
                if(t1 > t2)
                    j++;
                else if(t1 < t2)
                    k--;
                else//相等
                {
                    if(nums2[j] == nums2[k])//相等，直接Cn2结束
                    {
                        s += (k-j+1)*(k-j)/2;
                        break;
                    }
                    else
                    {
                        int l = nums2[j], r = nums2[k];
                        int ct1 = 0, ct2 = 0;
                        while(nums2[j] == l)
                        {
                            ct1++, j++;
                        }
                        while(nums2[k] == r)
                        {
                            ct2++, k--;
                        }
                        s += ct1*ct2;//左右相乘
                    }
                }
            }
        }
    }
};