一、四数相加 II
题目连接：https://leetcode.cn/problems/4sum-ii/
思路：将前两个数组的每个元素的和当key放入到hashMap, 在遍历后两个数组的和，然后看负的后两个数之和是否在上面的hashMap中，如果有则将value加入到最终的和内
class Solution {
public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
HashMap<Integer, Integer> hashMap = new HashMap<>();
for (int num1:nums1){
for (int num2:nums2) {
hashMap.put(num1 + num2, hashMap.getOrDefault(num1 + num2, 0) + 1);
}
}
int result = 0;
for (int num3:nums3){
for (int num4:nums4){
int temp = 0 - (num3 + num4);
if (hashMap.containsKey(temp)) {
result += hashMap.get(temp);
}
}
}
return result;
}
}
二、383. 赎金信
题目连接：https://leetcode.cn/problems/ransom-note/
思路一、使用hashMap
class Solution {
public boolean canConstruct(String ransomNote, String magazine) {
HashMap<Character, Integer> hashMap = new HashMap<>();
for (int i = 0; i < magazine.length(); i++){
hashMap.put(magazine.charAt(i), hashMap.getOrDefault(magazine.charAt(i), 0) + 1);
}
for (int i = 0; i < ransomNote.length(); i++){
char c = ransomNote.charAt(i);
if (hashMap.getOrDefault(c, 0) == 0) {
return false;
} else {
hashMap.put(c, hashMap.getOrDefault(c, 0) - 1);
}
}
return true;
}
}
思路二、使用数组
class Solution {
public boolean canConstruct(String ransomNote, String magazine) {
int[] hash = new int[26];
for (int i = 0; i < magazine.length(); i++) {
hash[magazine.charAt(i) - 'a']++;
}
for (int i = 0; i < ransomNote.length(); i++){
hash[ransomNote.charAt(i) - 'a']--;
if (hash[ransomNote.charAt(i) - 'a'] < 0) return false;
}
return true;
}
}
三、15. 三数之和
题目连接：https://leetcode.cn/problems/3sum/
思路一：固定一个nums[i], 在set中寻找（0 - nums[i] - nums[j]），找的到放入结果集result中，找不到将nums[j]放入set中
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
Arrays.sort(nums);
List<List<Integer>> result = new ArrayList<>();
HashSet<Integer> hashSet = new HashSet<>();
for (int i = 0; i < nums.length; i++){
if (nums[i] > 0) break;
if (i > 0 && (nums[i] == nums[i - 1])) {
continue;
}
hashSet.clear();
for (int j = i + 1; j < nums.length; j++){
if (j > i + 2
&& nums[j] == nums[j-1]
&& nums[j-1] == nums[j-2]) {
continue;
}
int c = 0 - (nums[i] + nums[j]);
if (hashSet.contains(c)) {
ArrayList<Integer> list = new ArrayList<>();
list.add(c);
list.add(nums[i]);
list.add(nums[j]);
result.add(list);
hashSet.remove(c);
} else {
hashSet.add(nums[j]);
}
}
}
return result;
}
}
思路二、双指针法，先排序，固定一个nums[i], int sum = nums[i] + nums[left] + nums[right]， 如果sum > 0，则right--,如果sum < 0， 则left++，相等则加入结果集中，注意去重
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]) 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<Integer> list = new ArrayList<>();
list.add(nums[i]);
list.add(nums[left]);
list.add(nums[right]);
result.add(list);
while (left < right && nums[left] == nums[left + 1]) {
left++;
}
while (left < right && nums[right] == nums[right - 1]) {
right--;
}
left++;
right--;
}
}
}
return result;
}
}
四、18. 四数之和
题目连接：https://leetcode.cn/problems/4sum/
思路：和三个数之和相同，固定一个两个nums[i] nums[j]，int sum = nums[i] + nums[j] + nums[left] + nums[right]，如果sum > 0 ,则right--,如果sum < 0, 则left++,
如果相同怎放入结果集中，注意去重
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++) {
if (nums[i] > 0 && nums[i] > target) return result;
if (i > 0 && nums[i] == nums[i - 1]) continue;
for (int j = i + 1; j < nums.length; j++) {
if (j > i + 1 && nums[j] == nums[j - 1]) continue;
int left = j + 1;
int 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 {
List<Integer> list = new ArrayList<>();
list.add(nums[i]);
list.add(nums[j]);
list.add(nums[left]);
list.add(nums[right]);
result.add(list);
while (left < right && nums[left] == nums[left + 1]) {
left++;
}
while (left < right && nums[right] == nums[right - 1]) {
right--;
}
left++;
right--;
}
}
}
}
return result;
}
}
网友评论