leetcode【888-公平的糖果棒交换】思考、优化、改进

谁践踏了优雅 2022-10-26 14:26 141阅读 0赞

声 明 ： 该 系 列 是 我 的 随 笔 ， 会 记 录 一 些 刷 题 的 感 受 ， 思 路 。 文 章 难 免 有 错 误 或 语 句 不 够 严 谨 ， 欢 迎 指 正 。 \\color\{\#FF0000\}\{声明：该系列是我的随笔，会记录一些刷题的感受，思路。文章难免有错误或语句不够严谨，欢迎指正。 \} 声明：该系列是我的随笔，会记录一些刷题的感受，思路。文章难免有错误或语句不够严谨，欢迎指正。  
 如 果 读 者 关 于 这 道 题 有 其 他 疑 问 ， 也 欢 迎 在 评 论 区 和 我 讨 论 我 会 及 时 回 复 ， 互 相 进 步 ， 谢 谢 ！ \\color\{\#FF0000\}\{如果读者关于这道题有其他疑问，也欢迎在评论区和我讨论我会及时回复，互相进步，谢谢！\} 如果读者关于这道题有其他疑问，也欢迎在评论区和我讨论我会及时回复，互相进步，谢谢！

2月1日的每日一题，又是ALICE和BOB搞事情。拿到这个题思路应当是比较明确的。抽象为数学模型：从A中选择一个数，从B中选择一个数，交换后使得A的总和等于B的总和。一个很容易想出来的思路是先计算出A，B当前总和，再求差得出derta1，在A,B中找两个数字使得他们的差值为-derta1。

class Solution { 
    public:
        vector<int> fairCandySwap(vector<int>& A, vector<int>& B) { 
    	sort(A.begin(),A.end());
    	sort(B.begin(),B.end());
    	int sumA = 0,sumB = 0,derta,dertaN;
    	for(int i =0;i!=A.size();++i)
    	    sumA += A[i];	
        for(int i =0;i!=B.size();++i)
            sumB += B[i];
    	derta = (sumA-sumB)/2;
    	int i = 0;
    	int j = 0;
    	while(dertaN!= derta)
        { 
    		dertaN = A[i] - B[j];
    		if(dertaN>derta)
    			j++;
    		if(dertaN<derta)
    			i++;
        }
        	return { A[i],B[j]};
    }};

这是一个经典的双指针问题，只需注意一些细节：  
1.A数组和B数组长度不一定相同，要分别计算，也可以使用accumulate函数  
2.本身数组是无序的需要sort函数排序，这就使得时间复杂度变为O(nlogn)。 所以这个题排序应当不是最优解。  
![在这里插入图片描述][20210202162746200.png]  
结果还行，相必应当是数据集太小了。不然选用官方的HASH表做法应当更好。

[20210202162746200.png]: /images/20221024/7a84eed8ce964a10b7762f73f560c844.png