Biweekly-Contest-123

1. 排序
2. 判断三角形是否存在
3. 判断是什么三角形

#灵神题解T1

• 同T4
  #灵神题解T2

前缀和

s[0]=0
s[1]=nums[0]
s[2]=nums[0]+nums[1]
...
s[i]=nums[0]+...+nums[i-1]
s[i+1]=nums[0]+...+nums[i]
nums[i]+...+nums[j]
=nums[0]+...+nums[j]-(nums[0]+...+nums[i-1])
=s[j+1]-s[i]
Copy

计算的最大值
枚举 ，问题变成计算的最小值
或者
哈希表

class Solution {
public:
	long long maximumSubarraySum(vector<int>& nums, int k) {
		unordered_map<int,long long > min_s;
		long long ans=LLONG_MIN;
		long long s=0;
		for(int x:nums){
			auto it =min_s.find(x+k);
			if(it != min_s.end()){
				ans=max(ans,s+x-it->second);
			}
			it =min_s.find(x-k);
			if(it !=min_s.end()){
				ans=max(ans,s+x-it->second);
			}
			it =min_s.find(x);
			if(it==min_s.end()||s<it->second){
				min_s[x]=s;
			}
			s+=x;
		}
		return ans==LLONG_MIN?0:ans;
}

};
Copy

#灵神题解T3

class Solution: 
	def maximumSubarraySum(self, nums: List[int], k: int) -> int: 			ans = -inf 
		min_s = defaultdict(lambda: inf) 
		s = 0 
		for x in nums: 
			min_s[x] = min(min_s[x], s)
			s += x 
			ans = max(ans, s-min(min_s[x - k], min_s[x + k]))
		return ans if ans > -inf else 0 
Copy

class Solution {
public:
	int numberOfPairs(vector<vector<int>> &points) {
		ranges::sort(points, [](const auto &p, const auto &q) {
			return p[0] != q[0] ? p[0] < q[0] : p[1] > q[1];	
		});
		int ans = 0, n = points.size();
		for (int i = 0; i < n; i++) {
			int y0 = points[i][1];
			int max_y = INT_MIN;
			for (int j = i + 1; j < n; j++) {
				int y = points[j][1];
				if (y <= y0 && y > max_y) {
					max_y = y;
					ans++;
				}
			}
		}
		return ans;
	}
};
Copy

#灵神题解T4