代码随想录算法训练营第六天|力扣454.四数相加II、力扣383.赎金信、力扣15.三数之和、力扣18.四数之和

四数相加II(力扣454.)

• 前两个数组的值直接遍历，并将和存入map中，key为和，value为出现次数
• 后两个数组再次遍历，在map中寻找是否存在0-(c+d)，若存在，count+=value
• for(a:A){//遍历AB
• for(b:B){
• map[a+b]++;}}//insert操作
• for(c:C){
• for(d:D){
• target = 0 - (c+d);
• if(map.containsKey(target){
• count += map.get(target);})}}

//先令前两个数组的和存在一个map中，key为值，value为得到次数；
//再次对后两个数组遍历，寻找是否有满足条件的值，count+=value；
//运用map.getOrDefault(num,0)表示返回value值或是默认值0
class Solution {
    public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
        int result = 0;
        Map<Integer,Integer> map = new HashMap<>();
        for(int a : nums1){
            for(int b : nums2){
                map.put(a+b,map.getOrDefault(a+b,0) + 1);//返回value值，若无，则返回默认值
            }
        }
        for(int c : nums3){
            for(int d : nums4){
                int target = 0 - (c + d);
                result += map.getOrDefault(target,0);
            }
        }
        return result;
    }
}

赎金信(力扣383.)

• 索引确定用数组的哈希，toCharArray()将字符串转换为字符数组

class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        //特殊情况的边界条件一定要考虑
        if(ransomNote.length() > magazine.length()){
            return false;
        }
        int[] arr = new int[26];
        //toCharArray()将字符串转换为字符数组
        for(char a : magazine.toCharArray()){
            arr[a - 'a']++;
        }
        for(char b : ransomNote.toCharArray()){
            arr[b - 'a']--;
        }
        for(int count : arr){
            if(count < 0){
                return false;
            }
        }
        return true;
    }
}

三数之和(力扣15.)

• 双指针法

• 对数组进行排序

• 从头开始遍历i

• 如果nums[i]>0,return;//target结果为0，此为正则不可能

• 和前一位比较，如果相同值则跳过且i>0//去重操作

• left = i+1；right = nums.size - 1;

• while(right > left){

• //遍历

• if( > 0) right--;

• if( < 0) left++;

• else{

• result.push(nums[i],nums[left],nums[right])}

• while(right>left&&right[i]==right[i-1])right--;

• while(right>left&&left[i]==left[i+1])}

• //在插入正确答案后，以上对b和c进行去重，其逻辑与对a去重相反

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(nums);
        for(int i = 0;i < nums.length;i++){
            if(nums[i] > 0){
                return result;
            }
            if(i>0&&nums[i]==nums[i-1]){//去除a
                continue;
                //i++;
            }
            int left = i+1;
            int right = nums.length - 1;
            while(right > left){
                if(nums[i] + nums[left] + nums[right] > 0){
                    right--;
                }else if(nums[i] + nums[left] + nums[right] < 0){
                    left++;
                }else{
                    result.add(Arrays.asList(nums[i],nums[left],nums[right]));
                //在result插入正确答案后，去重b和c
                while(right>left && nums[right] == nums[right - 1]){
                    right--;
                }
                while(right>left && nums[left] == nums[left + 1]){
                    left++;
                }
                left++;
                right--;
                }   
            }
        }
        return result;
    }
}

四数之和(力扣18.)

• 在三数之和的基础上新加一个数，要注意对每个数字都要进行去重操作
• 剪枝操作要慎重，考虑到每个数大于零的情况

class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        Arrays.sort(nums);
        List<List<Integer>> result = new ArrayList<>();
        if(nums.length < 4){
            return result;
        }
        for(int i = 0; i < nums.length;i++){
            //剪枝必须满足nums[i]和target都大于0
            if(nums[i]>0&&target>0&&nums[i]>target){
                return result;
            }
            //去除多余i
            if(i > 0 && nums[i] == nums[i - 1]){
                continue;
            }
            for(int j = i+1;j<nums.length;j++){
                // if(nums[i]>0&&nums[j]>0&&target>0&&nums[i]+nums[j]>target){
                //     return result;
                // }
                //去除多余j
                if(j>i+1&&nums[j] == nums[j - 1]){
                    continue;
                }
                int left = j + 1 ;
                int right = nums.length - 1;
                
                while(right > left){
                    //num的赋值应该在循环里，因为它的值随着left，right变化而变化
                long num = (long)nums[i] + nums[j] + nums[left] + nums[right];
                if(num > target){
                    right--;
                }else if(num < target){
                    left++;
                }else{
                    result.add(Arrays.asList(nums[i],nums[j],nums[left],nums[right]));
                    //去除b、c
                    while(right>left&&nums[right] == nums[right - 1]){
                        right--;
                    }
                    while(right>left&&nums[left] == nums[left + 1]){
                        left++;
                    }
                    right--;
                    left++;
                }
            }
            }
        }
        return result;
    }
}