本文涉及的基础知识点

C++算法：滑动窗口及双指针总结 三指针

LeetCode825. 适龄的朋友

在社交媒体网站上有 n 个用户。给你一个整数数组 ages ，其中 ages[i] 是第 i 个用户的年龄。
如果下述任意一个条件为真，那么用户 x 将不会向用户 y（x != y）发送好友请求：
ages[y] <= 0.5 * ages[x] + 7
ages[y] > ages[x]
ages[y] > 100 && ages[x] < 100
否则，x 将会向 y 发送一条好友请求。
注意，如果 x 向 y 发送一条好友请求，y 不必也向 x 发送一条好友请求。另外，用户不会向自己发送好友请求。
返回在该社交媒体网站上产生的好友请求总数。
示例 1：
输入：ages = [16,16]
输出：2
解释：2 人互发好友请求。
示例 2：
输入：ages = [16,17,18]
输出：2
解释：产生的好友请求为 17 -> 16 ，18 -> 17 。
示例 3：
输入：ages = [20,30,100,110,120]
输出：3
解释：产生的好友请求为 110 -> 100 ，120 -> 110 ，120 -> 100 。

提示：
n == ages.length
1 <= n <= 2 * 10⁴
1 <= ages[i] <= 120

三指针

如果条件三成立，则条件二一定成立，故条件三是多余的。
$\forall$y, ages[y] <= 0.5 * ages[x] + 7,x等于x2时，不等式成立。则x > x2时也成立。求最小x，令其为x2。则y不需要向年龄ages[x2…n-1]的用户发送请求。
$\forall$y, ages[y] > ages[x] ，令不等式成立的最大x为x1。则x < x1时，不等式也成立。故ages[0…x1]不需要发送。
$\forall$y，令不需要发送的数量为cur:
如果x1 >= x2-1。则所有用户都不需要发送。
若干ages[x2…n-1]包括ages[y]，则所有玩家都不需要发送。
故排除以上两种情况后：
cur = (x1+1)+1 + (n-x2)
结果：n$\times$n - $\sum$cur。
指针一：y。从0到n-1
指针二：x3=x1+1，从0到大。
指针三：x2，从0到大。.
时间复杂度：O(nlogn)
ages[x3] >= ages[y]。

代码

核心代码

class Solution {
		public:
			int numFriendRequests(vector<int>& ages) {
				const int N = ages.size();
				sort(ages.begin(), ages.end());
				int ret = 0;
				for (int y = 0,x3=0,x2=0; y < N;y++) {
					while ((x3<N)&&(ages[x3] < ages[y])) { x3++; }
					while ((x2<N) && (0.5 * ages[x2] + 7< ages[y])) { x2++;}
					if ((x3 >= x2 ) || (y >= x2 )) { ret += N; continue; }
					ret += x3 + 1 + (N-x2);
				}
				return N*N-ret;
			}				
		};

单元测试用例

TEST_CLASS(LeetCode825)
	{
		//LeetCode825. 适龄的朋友
		class Solution {
		public:
			int numFriendRequests(vector<int>& ages) {
				sort(ages.begin(), ages.end());
				int ret = 0;
				for (const auto& n : ages) {
					if (n >= 2* n - 14) { continue; }
					auto it1 = lower_bound(ages.begin(), ages.end(), n);
					auto it2 = lower_bound(ages.begin(), ages.end(), 2*n-14);
					ret += it2 - it1;		
					ret--;	
				}
				return ret ;
			}
			int Test(vector<int>& ages) {
				int ret = 0;
				sort(ages.begin(), ages.end());
				for (int y = 0; y < ages.size(); y++) {
					Logger::WriteMessage(("\r\n" + std::to_string(ages[y])+"\r\n").c_str());
					for (int x = 0; x < ages.size(); x++) {
						if (y == x) { continue; }
						if (ages[y] <= 0.5 * ages[x] + 7) { continue; }
						if (ages[y] > ages[x]) { continue; }
						ret++;
						Logger::WriteMessage((" " + std::to_string(ages[x])).c_str());
					}
				}
				return ret;
			}
		};
	public:
		vector<int> ages;
		TEST_METHOD(TestMethod1)
		{
			ages = { 5 };
			auto res = Solution().numFriendRequests(ages);
			AssertEx(0, res);
		}
		TEST_METHOD(TestMethod2)
		{
			ages = { 20 };
			auto res = Solution().numFriendRequests(ages);
			AssertEx(0, res);
		}
		TEST_METHOD(TestMethod3)
		{
			ages = { 11,12 };
			auto res1 = Solution().Test(ages);
			auto res = Solution().numFriendRequests(ages);
			AssertEx(res1, res);
		}
		TEST_METHOD(TestMethod11)
		{
			ages = { 16, 16 };
			auto res = Solution().numFriendRequests(ages);
			AssertEx(2, res);
		}
		TEST_METHOD(TestMethod12)
		{
			ages = { 16, 17,18 };
			auto res = Solution().numFriendRequests(ages);
			AssertEx(2, res);
		}
		TEST_METHOD(TestMethod13)
		{
			ages = { 20,30,100,110,120 };
			auto res = Solution().numFriendRequests(ages);
			AssertEx(3, res);
		}
		TEST_METHOD(TestMethod14)
		{
			ages = { 108,115,5,24,82 };
			auto res = Solution().numFriendRequests(ages);
			AssertEx(3, res);
		}
		TEST_METHOD(TestMethod15)
		{
			ages = { 101,98,80,20,1,97,3,77,114,109 };			
			auto res1 = Solution().Test(ages);
			auto res = Solution().numFriendRequests(ages);
			AssertEx(res1, res);
		}
	};