首页 > 其他分享 >day7

day7

时间:2023-01-18 00:45:08浏览次数:33  
标签:right nums int day7 sum && left

1、leetcode454 四数相加

  1. 代码实现

    class Solution {
        public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
            HashMap<Integer,Integer> sumOfNums1AndNums2 = new HashMap<Integer,Integer>();//key:数组1和数组2的元素之和sum  value:sum的出现次数
            int count = 0;
    
    
            for(num1 : nums1){
                for(num2 : nums2){
                    int sum = num1 + num2;
                    if(sumOfNums1AndNums2.containsKey(sum)){
                        sumOfNums1AndNums2.put(sum,sumOfNums1AndNums2.get(sum)+1);
                    } else {
                        sumOfNums1AndNums2.put(sum,1);
                    }
                }
            }
    
            for(num3 : nums3){
                for(num4 : nums4){
                    sum = num3 + num4;
                    if(sumOfNums1AndNums2.containsKey(0-sum)){
                        count += sumOfNums1AndNums2.get(0-sum);
                    }
                }
            }
    
            return count;
        }
    }
    

2、leetcode383 赎金信

  1. 代码实现

    class Solution {
        public boolean canConstruct(String ransomNote, String magazine) {
            int[] src = new int[26];
            
            for(int i=0; i<magazine.length(); i++){
                src[magazine.charAt(i) - 'a']++; 
            }
    
            for(int i=0; i<ransomNote.length();i++){
                src[ransomNote.charAt(i)-'a']--;
                if(src[ransomNote.charAt(i)-'a'] < 0){
                    return false;
                }
            }
    
            return true;
        }
    }
    

3、leetcode15 三数之和

  1. 代码实现

    class Solution {
        public List<List<Integer>> threeSum(int[] nums) {
            List<List<Integer>> res = new ArrayList<>();
    
            Arrays.sort(nums);
    
            for(int i=0; i<nums.length; i++){
                //jian'zhi
                if(nums[i] > 0){
                    return res;
                }
                if(i > 0 && nums[i] == nums[i-1]){//对i进行去重
                    continue;
                }
    
                int left = i+1;
                int right = nums.length - 1;
    
                while(right > left){
                    int sum = nums[i] + nums[left] + nums[right];
                    if(sum>0){
                        right--;
                    } else if(sum<0) {
                        left++;
                    } else {
                        res.add(Arrays.asList(nums[i], nums[left], nums[right]));
                        //在确保有一个结果集的前提下,对left、right进行去重
                        while (right > left && nums[right] == nums[right - 1]) right--;
                        while (right > left && nums[left] == nums[left + 1]) left++;
    
                        right--;
                        left++;
                    }
                }
            }
            return res;
    
        }
    }
    

4、leetcode18 四数之和

  1. 代码实现【在三数之和的基础上增加一层for循环】

    class Solution {
        public List<List<Integer>> fourSum(int[] nums, int target) {
           List<List<Integer>> res = new ArrayList<>();
           Arrays.sort(nums);
    
           for(int k=0; k<nums.length; k++){
               //剪枝操作
               if(nums[k]>target && nums[k]>0){
                   break;
               }
    
                //对nums[k]去重
               if(k>0 && nums[k]==nums[k-1]){
                   continue;
               }
    
               for(int i=k+1; i<nums.length; i++){
                   //剪枝操作
                   if(nums[k]+nums[i]>target && (nums[k]+nums[i])>=0){
                       break;
                   }
                   //对nums[i]去重
                   if(i>k+1 && nums[i]==nums[i-1]){
                       continue;
                   }
                   int left = i+1;
                   int right = nums.length-1;
    
                   while(right>left){
                       if(nums[k]+nums[i]+nums[left]+nums[right]>target){
                           right--;
                       } else if (nums[k]+nums[i]+nums[left]+nums[right]<target) {
                            left++;
                       } else {
                           res.add(Arrays.asList(nums[k],nums[i],nums[left],nums[right]));
                           //对left、right进行去重
                           while(right>left && nums[right]==nums[right-1]) right--;
                           while(right>left && nums[left]==nums[left+1]) left++;
    
                            right--;
                            left++;
                       }
                   }
               }
           } 
           return res;
    
        }
    }
    

标签:right,nums,int,day7,sum,&&,left
From: https://www.cnblogs.com/hzj-bolg/p/17058996.html

相关文章

  • 刷刷刷Day7| 18. 四数之和
    18.四数之和LeetCode题目要求给你一个由n个整数组成的数组 nums,和一个目标值target。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a],nums[b],nums......
  • 刷刷刷Day7| 15. 三数之和
    15.三数之和LeetCode题目要求给你一个整数数组nums,判断是否存在三元组[nums[i],nums[j],nums[k]]满足i!=j、i!=k且j!=k,同时还满足nums[i]+nums[j]+......
  • 代码随想录day7 LeetCode 454. 四数相加 II 383. 赎金信 15.三数之和 18四数之和
    454.四数相加IIhttps://leetcode.cn/problems/4sum-ii/采用哈希表法,能比暴力法减少时间复杂度,先用两个数之和做出哈希表,再用剩下两数之和寻找哈希表中的数classSolu......
  • 刷刷刷Day7| 383. 赎金信
    383.赎金信LeetCode题目要求给你两个字符串:ransomNote和magazine,判断ransomNote能不能由magazine里面的字符构成。如果可以,返回true;否则返回false。magaz......
  • LOJ 6041 「雅礼集训 2017 Day7」事情的相似度 题解 (SAM+启发式合并)
    题目链接首先很容易想到的是对反串求SA和LCP,然后询问就是求起点在某个区间内的所有后缀两两LCP的最大值,可以用莫队解决,时间复杂度\(O(n\sqrtnlogn)\),应该是过不了的。......
  • day7-2022.12.17-Webstorm基本设置
    一、快捷键设置1、点击左上角的File->settings,在输入框中查找Keymap,选择Eclipse,此处是改变快捷键的方式。Ctrl+F:本Vue文件内查找Ctrl+H:全文件查找  ......
  • day7
    ......
  • Day7 - 面向对象编程进阶
    本节内容:面向对象高级语法部分经典类vs新式类静态方法、类方法、属性方法类的特殊方法反射异常处理Socket开发基础作业:开发一个支持多用户在线的FTP程序 1.经典类......
  • javascript-代码随想录训练营day7
    454.四数相加Ⅱ题目链接:https://leetcode.cn/problems/4sum-ii/题目描述:给你四个整数数组nums1、nums2、nums3和nums4,数组长度都是n,请你计算有多少个元组(i,j,......
  • Day7
    上午题题目:AGC058D虑定义一个连续的\(abc,bca,cab\)是极长的上升子段,考虑若干个极长的上升子段一定是不交的,所以这么定义没有问题。考虑容斥,顷定有\(k\)个极长上......