代码随想录Day07

lc454

class Solution {
    public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
  Map<Integer,Integer> abmap=new HashMap<>();
        for (int i = 0; i < nums1.length; i++) {
            for (int j = 0; j < nums2.length; j++) {
                if (!abmap.containsKey(nums1[i]+nums2[j])){
                    abmap.put(nums1[i]+nums2[j],1);
                }else{
                    Integer integer = abmap.get(nums1[i] + nums2[j]);
                    integer++;
                    abmap.put(nums1[i] + nums2[j],integer);
                }
            }
        }
        int count=0;
        for (int i = 0; i < nums3.length; i++) {
            for (int j = 0; j < nums4.length; j++) {
                if (abmap.containsKey(-nums3[i] - nums4[j])){
                    count+=abmap.get(-nums3[i] - nums4[j]);
                }
            }
        }

        return count;
    }
}

lc383

class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
 
     if (magazine.length() < ransomNote.length()) {
        return false;
    }

    Map<Character, Integer> map = new HashMap<>();
    for (int i = 0; i < ransomNote.length(); i++) {
        char ran = ransomNote.charAt(i);
        map.put(ran, map.getOrDefault(ran, 0) + 1);
    }

    for (int i = 0; i < magazine.length(); i++) {
        char c = magazine.charAt(i);
        if (map.containsKey(c)) {
            if (map.get(c) <= 0) {
                continue;
            } else {
                map.put(c, map.get(c) - 1);
            }
        }
    }

    for (int count : map.values()) {
        if (count > 0) {
            return false;
        }
    }

    return true;
    }
}

lc15

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
  List<List<Integer>> list=new ArrayList<>();
        Arrays.sort(nums);
        for (int i = 0; i < nums.length; i++) {
            if (nums[i]>0){
                return list;
            }

            if (i>0 && nums[i]==nums[i-1]){
                continue;
            }

            int left=i+1;
            int right= nums.length-1;

            while (left<right){
                int sum=nums[i]+nums[left]+nums[right];
                if (sum>0){
                    right--;
                }else if (sum<0){
                    left++;
                }else{
                    list.add(Arrays.asList(nums[i],nums[left],nums[right]));
                    //执行去重逻辑
                    while (left<right && nums[right]==nums[right-1]){
                        right--;
                    }
                    while (left<right && nums[left]==nums[left+1]){
                        left++;
                    } 
                    right--;
                left++;
                }
               
            }
        }
        return list;
    }
}

lc18

class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(nums);
       
        for (int i = 0; i < nums.length; i++) {
		
            // nums[i] > target 直接返回, 剪枝操作
            if (nums[i] > 0 && nums[i] > target) {
                return result;
            }
		
            if (i > 0 && nums[i - 1] == nums[i]) {    // 对nums[i]去重
                continue;
            }
            
            for (int j = i + 1; j < nums.length; j++) {

                if (j > i + 1 && nums[j - 1] == nums[j]) {  // 对nums[j]去重
                    continue;
                }

                int left = j + 1;
                int right = nums.length - 1;
                while (right > left) {
		    // nums[k] + nums[i] + nums[left] + nums[right] > target int会溢出
                    long sum = (long) nums[i] + nums[j] + nums[left] + nums[right];
                    if (sum > target) {
                        right--;
                    } else if (sum < target) {
                        left++;
                    } else {
                        result.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));
                        // 对nums[left]和nums[right]去重
                        while (right > left && nums[right] == nums[right - 1]) right--;
                        while (right > left && nums[left] == nums[left + 1]) left++;

                        left++;
                        right--;
                    }
                }
            }
        }
        return result;
    }
}