算法练习第七天|454.四数相加II、383. 赎金信、15. 三数之和、18. 四数之和

hash表【index.php/tags-41973.html" >���组、map】以及双指针的运用

454.四数相加II

public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {        //nums1,nums2的和作为key，出现次数记位value        Map map = new HashMap();        for(int a : nums1){            for(int b: nums2){                int sum = a+b;                map.put(sum,map.getOrDefault(sum,0)+1);            }        }        int sum = 0;        for(int a : nums3){            for(int b: nums4){                sum += map.getOrDefault(0-a-b,0);            }        }        return sum;    }

1. 赎金信

    public boolean canConstruct(String ransomNote, String magazine) {        if(ransomNote.length() > magazine.length()){            return false;        }        int[] record = new int[26];        for(int i = 0; i 
三数之和
public List threeSum(int[] nums) {        List res = new ArrayList();        Arrays.sort(nums);        for(int i=0; i 0){                return res;            }            if(i> 0&& nums[i] == nums[i- 1]){                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 left&& nums[right] == nums[right-1]) right--;                    while(right>left&& nums[left] == nums[left+1]) left ++ ;                    left++;                    right--;                }            }        }        return res;    }
 
四数之和
class Solution {    public List fourSum(int[] nums, int target) {        List res = new ArrayList();        Arrays.sort(nums);        for(int i=0; i 0 && nums[i] > target){                return res;            }            if(i> 0&& nums[i] == nums[i- 1]){                continue;            }            for(int j=i+1; j i+1&& nums[j] == nums[j- 1]){                    continue;                }                int left = j+1;                int right = nums.length-1;                while(right > left){                    int sum = nums[i] +nums[j] + nums[left]+ nums[right];                    if(sum> target){                        right--;                    }else if(sum left&& nums[right] == nums[right-1]) right--;                        while(right>left&& nums[left] == nums[left+1]) left ++ ;                        left++;                        right--;                    }                }            }          }        return res;    }}