Day56| 灵神 | 相向双指针：统计和小于目标的下标对数目&&最接近的三数之和

2824.统计和小于目标的下标对数目

2824. 统计和小于目标的下标对数目 - 力扣（LeetCode）

思路：

和两数之和思路一样

大了就r–

小了就收集答案

完整代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int countPairs(vector<int>& nums, int target) {
        sort(nums.begin(),nums.end());
        int res=0;
        int l=0,r=nums.size()-1;
        while(l<r)
        {
            if(nums[l]+nums[r]>=target)
                r--;
            else
            {
                res+=(r-l);
                l++;
            }
        }
        return res;
    }
};

记录一下自己写的，上面的版本是灵神的答案，把我的优化了，其实就是没想到l在取过答案以后，r就不可能从最后开始了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int countPairs(vector<int>& nums, int target) {
        sort(nums.begin(),nums.end());
        int res=0;
        for(int i=0;i<nums.size()-1;i++)
        {
            int l=i,r=nums.size()-1;
            while(l<r)
            {
                if(nums[l]+nums[r]>=target)
                    r--;
                else
                {
                    res+=(r-l);
                    break;
                }
            }
        }
        return res;
    }
};

16.最接近的三数之和

16. 最接近的三数之和 - 力扣（LeetCode）

思路：

和三数之和思路类似，甚至不需要去重，所以更加简单。

只需要增加一个变量x来记录三个数的和与target之间的最小差值就是了

只要target和三数之和的差值小于x，那就更新x和最后返回的答案

完整代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
        sort(nums.begin(),nums.end());
        int res=0;
        int minTemp=INT_MAX;
        for(int i=0;i<nums.size()-2;i++)
        {
            int l=i+1,r=nums.size()-1;
            while(l<r)
            {
                int cur=nums[i]+nums[r]+nums[l];
                if(cur>target)
                {
                    if(cur-target<minTemp)
                    {
                        minTemp=cur-target;
                        res=cur;
                    }
                    r--;    
                }
                else if(cur<target)
                {
                    if(target-cur<minTemp)
                    {
                        minTemp=target-cur;
                        res=cur;
                    }
                    l++;
                }
                else
                    return cur;
            }
        }
        return res;
    }
};