1、leetcode454 四数相加
-
代码实现
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 赎金信
-
代码实现
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 三数之和
-
代码实现
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 四数之和
-
代码实现【在三数之和的基础上增加一层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; } }