题目链接3020. 子集中元素的最大数量中等算法原理解法哈希表56ms击败84.73%时间复杂度O(N)整体思路将所有数扔进哈希表然后逐一遍历看这个数出现了几次如果出现1次就让 mx 和 1 更新最大值否则就继续探寻这里的探寻的意思如果这个数是 2那么就看 4是否存在①如果不存在退出探寻②如果存在更新 mx如果 4 只出现 1 次不再探寻了因为无法保证两边对称如果 4 出现≥ 2 次继续探寻这里更新的时候注意这里的幂数是2的 k 次幂因此取值的时候需要套两层 Math.pow()这个数就可以表示为Math.pow(key,Math.pow(2,k))我们后续更新 mx 的时候就可以通过 k 来更新拿 [ 2 , 4 , 16, 4 , 2 ]为例表示为 [ 2¹ , 2² , 2⁴ , 2² , 2¹ ] 这里 k 最大为 3那么长度就是 2 × 3 -1 5因此更新的长度表示为 2 × k 1特殊情况处理当 key 为 1 时1¹ 1、1² 1、1⁴ 1……因此这个时候只需要统计 1 的个数 n 即可n 为奇数mx max(mx,n)n 为偶数mx max(mx,n-1)细节使用 Math.pow() 时要注意精度转换将 double 强制转换成 intJava代码class Solution { //3020. 子集中元素的最大数量 public int maximumLength(int[] nums) { if(nums.length0) return 0; MapInteger,Integer hashnew HashMap(); for(int x:nums) hash.merge(x,1,Integer::sum); int mx1; for(Map.EntryInteger,Integer entry:hash.entrySet()){ int keyentry.getKey(); int valentry.getValue(); //特殊处理1 if(key1){ int nhash.get(1); if(n%21) mxMath.max(mx,n); else mxMath.max(mx,n-1); continue; } if(val1){ mxMath.max(mx,1); continue; } int k1; while(hash.containsKey((int)Math.pow(key,Math.pow(2,k)))){ mxMath.max(mx,2*k1); if(hash.get((int)Math.pow(key,Math.pow(2,k)))1) break; k; } } return mx; } }
题目链接3020. 子集中元素的最大数量中等算法原理解法哈希表56ms击败84.73%时间复杂度O(N)整体思路将所有数扔进哈希表然后逐一遍历看这个数出现了几次如果出现1次就让 mx 和 1 更新最大值否则就继续探寻这里的探寻的意思如果这个数是 2那么就看 4是否存在①如果不存在退出探寻②如果存在更新 mx如果 4 只出现 1 次不再探寻了因为无法保证两边对称如果 4 出现≥ 2 次继续探寻这里更新的时候注意这里的幂数是2的 k 次幂因此取值的时候需要套两层 Math.pow()这个数就可以表示为Math.pow(key,Math.pow(2,k))我们后续更新 mx 的时候就可以通过 k 来更新拿 [ 2 , 4 , 16, 4 , 2 ]为例表示为 [ 2¹ , 2² , 2⁴ , 2² , 2¹ ] 这里 k 最大为 3那么长度就是 2 × 3 -1 5因此更新的长度表示为 2 × k 1特殊情况处理当 key 为 1 时1¹ 1、1² 1、1⁴ 1……因此这个时候只需要统计 1 的个数 n 即可n 为奇数mx max(mx,n)n 为偶数mx max(mx,n-1)细节使用 Math.pow() 时要注意精度转换将 double 强制转换成 intJava代码class Solution { //3020. 子集中元素的最大数量 public int maximumLength(int[] nums) { if(nums.length0) return 0; MapInteger,Integer hashnew HashMap(); for(int x:nums) hash.merge(x,1,Integer::sum); int mx1; for(Map.EntryInteger,Integer entry:hash.entrySet()){ int keyentry.getKey(); int valentry.getValue(); //特殊处理1 if(key1){ int nhash.get(1); if(n%21) mxMath.max(mx,n); else mxMath.max(mx,n-1); continue; } if(val1){ mxMath.max(mx,1); continue; } int k1; while(hash.containsKey((int)Math.pow(key,Math.pow(2,k)))){ mxMath.max(mx,2*k1); if(hash.get((int)Math.pow(key,Math.pow(2,k)))1) break; k; } } return mx; } }
