No.1
题目
思路
- 很妙的办法:有四个数组A、B、C、D,用hashMap记录【A、B中数字之和】+【这些和出现的次数】,再遍历C、D中数字组合,寻找【0-C、D中数字之和】在hashMap中出现的次数,并累加
- 本质上,这是把4个数组简化成了2个数组
代码
public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
// 记录A、B中元素之和+出现次数
Map<Integer, Integer> ABhash = new HashMap<>();
int targetCount = 0;
for (int i = 0; i < nums1.length; i++) {
for (int j = 0; j < nums2.length; j++) {
// 取出“和”+1,统计“和”出现次数
ABhash.put(nums1[i] + nums2[j], ABhash.getOrDefault(nums1[i] + nums2[j], 0) + 1);
}
}
for (int i = 0; i < nums3.length; i++) {
for (int j = 0; j < nums4.length; j++) {
if (ABhash.containsKey(-nums3[i] - nums4[j]))
targetCount += ABhash.get(-nums3[i] - nums4[j]);
}
}
return targetCount;
}
No.2
题目
思路
- 用一个int[]记录magazine中字母出现次数
- 遍历ransomNote,消耗可用字母数
- 出现负值,就是不够用,可以返回false
代码
public boolean canConstruct(String ransomNote, String magazine) {
// 记录26个字母的出现次数
int[] alphabet = new int[26];
// 统计可用字母数量
for (int i = 0; i < magazine.length(); i++) {
char item = magazine.charAt(i);
alphabet[item - 'a']++;
}
// 消耗字母
for (int i = 0; i < ransomNote.length(); i++) {
char item = ransomNote.charAt(i);
// 不够用,false
if (--alphabet[item - 'a'] < 0)
return false;
}
return true;
}
No.3
题目
思路
- 先升序排序,因为有序的数组,相同的数字一定靠在一起,这样就可以跳过重复的数字,从而去重
- 升序排序后,第一个数字大于target,就不用找了,返回空数组
- 升序排序后,最后一个数字小于target,就不用找了,返回空数组
- 双指针法
- 对数字a、b、c都要去重
- 参看去重逻辑的思考
代码
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> result = new ArrayList<>(); // 存结果
Arrays.sort(nums); // 先排序
// 升序数组,最小元素大于0或者最大元素小于0,都没有必要再找了
if (nums[0] > 0 || nums[nums.length - 1] < 0)
return result;
for (int i = 0; i < nums.length - 2; i++) {
// 去重
if (i > 0 && nums[i] == nums[i - 1])
continue;
int left = i + 1, right = nums.length - 1;
while (left < right) {
int sum = nums[i] + nums[left] + nums[right];
if (sum < 0) {
left++;
} else if (sum > 0) {
right--;
} else {
result.add(new ArrayList<>(Arrays.asList(nums[i], nums[left], nums[right])));
// 去重
while (left < right && nums[left] == nums[left + 1]) left++;
while (left < right && nums[right] == nums[right - 1]) right--;
// 找到答案,双指针同时变化
left++;
right--;
}
}
}
return result;
}
No.4
题目
思路
- 相比三数之和,和从0变成了target,思路还是类似
- 去重的细节要特别注意
- 需要仔细考虑双指针去重逻辑
代码
public List<List<Integer>> fourSum(int[] nums, int target) {
Arrays.sort(nums); // 排序
List<List<Integer>> result = new ArrayList<>(); // 存结果
// 最小的数字大于target,不能找到和为target的数
if (nums[0] > target)
return result;
for (int i = 0; i < nums.length - 3; i++) {
// 剪枝,访问过nums[0]之后再判重
if (i > 0 && nums[i] == nums[i - 1]) continue;
for (int j = i + 1; j < nums.length - 2; j++) {
// 剪枝,访问过nums[i+1]之后再判重
if (j > i + 1 && nums[j] == nums[j - 1]) continue;
int left = j + 1, right = nums.length - 1;
while (left < right) {
int sum = nums[i] + nums[j] + nums[left] + nums[right];
if (sum > target) right--;
else if (sum < target) left++;
else {
result.add(new ArrayList<>(Arrays.asList(nums[i], nums[j], nums[left], nums[right])));
// 去重
while (left < right && nums[left] == nums[left + 1]) left++;
while (left < right && nums[right] == nums[right - 1]) right--;
right--;
left++;
}
}
}
}
return result;
}
标签:right,nums,int,Day7,++,length,哈希,Leetcode,left
From: https://www.cnblogs.com/tomatoQt/p/17658083.html