公路水运建设质量与安全监督系统网站,深圳品牌策划机构,百度统计代码安装位置,网站正能量下载免费软件1、题目
给你一个整数数组 nums 。
如果一组数字 (i,j) 满足 nums[i] nums[j] 且 i j #xff0c;就可以认为这是一组 好数对 。
返回好数对的数目。
示例 1#xff1a;
输入#xff1a;nums [1,2,3,1,1,3] 输出#xff1a;4 解释#xff1a;有 4 组好数对 nums[j] 且 i j 就可以认为这是一组 好数对 。
返回好数对的数目。
示例 1
输入nums [1,2,3,1,1,3] 输出4 解释有 4 组好数对分别是 (0,3), (0,4), (3,4), (2,5) 下标从 0 开始 示例 2
输入nums [1,1,1,1] 输出6 解释数组中的每组数字都是好数对 示例 3
输入nums [1,2,3] 输出0
提示
1 nums.length 100 1 nums[i] 100
2、解
暴力解 int numIdenticalPairs(vectorint nums){int result 0;for(int i 0; i nums.size() - 1; i){for(int j i 1; j nums.size(); j){if(nums[i] nums[j]) result;}}return result;}另解 在题解里边看到的一个绝妙解 思路就是把nums中的每个数据看作temp数组的下标(该下标从1开始, 出现间隙不用管, 比如nums{2, 3, 7}, 对应temp{0, 1, 1, 0, 0 , 0 ,1}), 遍历nums然后把对应temp的位置做操作记录每个数据出现次数即可, 关于对数的话, 找到规律发现其实就是把每次遍历数据出现次数-1叠加起来。 比如{2, 3, 7}→{0, 1, 1, 0, 0 , 0 ,1}好数对为0 {2, 3, 72}→{0, 2, 1, 0, 0 , 0 ,1}好数对为1。 可以理解为第一次出现的数字就占了萝卜坑了如果后边再次出现就代表它刚好满足值相等且出现位置索引值是大于第一次出现该数字的索引值的遍历顺序本就是从小到大。 int numIdenticalPairsA(vectorint nums){int result 0;int temp[100] {};for(auto num : nums){result temp[num - 1];temp[num -1];}return result;}
