454 四数相加 4Sum II
要点
- 两组两组遍历，这样时间复杂度 O(N^2) 比起一三遍历 O(N^3) 要更低
- 由于题目要求计数，所以 map 里保存的应该是和相等的个数
代码
时间复杂度 O(N^2) 空间复杂度 O(N^2)
C++
class Solution {
public:
int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
unordered_map<int, int> nums12_map;
for (int i : nums1) {
for (int j : nums2) {
int tmp = i + j;
nums12_map[tmp]++;
}
}
int res = 0;
for (int i : nums3) {
for (int j : nums4) {
int tmp = - i - j;
if (nums12_map.find(tmp) != nums12_map.end()) {
res += nums12_map[tmp];
}
}
}
return res;
}
};
Python
class Solution:
def fourSumCount(self, nums1: List[int], nums2: List[int], nums3: List[int], nums4: List[int]) -> int:
size = len(nums1)
nums12_map = {}
for i in range(size):
for j in range(size):
tmp = nums1[i] + nums2[j]
if tmp in nums12_map.keys():
nums12_map[tmp] += 1
else:
nums12_map[tmp] = 1
res = 0
for i in range(size):
for j in range(size):
tmp = - nums3[i] - nums4[j]
if tmp in nums12_map.keys():
res += nums12_map[tmp]
return res
383 赎金信 Ransom Note
要点
这道题和字母异位词类似
代码
C++
class Solution {
public:
bool canConstruct(string ransomNote, string magazine) {
if (ransomNote.size() > magazine.size()) return false;
int hash_array[26] = {0};
for (char letter : magazine) {
hash_array[letter - 'a']++;
}
for (char letter : ransomNote) {
hash_array[letter - 'a']--;
}
for (int i = 0; i < 26; i++) {
if (hash_array[i] < 0) {
return false;
}
}
return true;
}
};
Python
class Solution:
def canConstruct(self, ransomNote: str, magazine: str) -> bool:
if len(magazine) < len(ransomNote):
return False
hash_list = [0 for i in range(26)]
for letter in magazine:
hash_list[ord(letter) - ord('a')] += 1
for letter in ransomNote:
hash_list[ord(letter) - ord('a')] -= 1
for i in range(26):
if hash_list[i] < 0:
return False
return True
15 三数之和 3Sum
要点
sort 然后双指针
代码
Python
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
if len(nums) < 3:
return []
nums.sort()
res = []
for i in range(len(nums) - 2):
if nums[i] > 0:
break
if i > 0 and nums[i] == nums[i - 1]:
continue
left = i + 1
right = len(nums) - 1
while left < right:
tmp = nums[i] + nums[left] + nums[right]
if tmp < 0:
left += 1
elif tmp > 0:
right -= 1
else:
res.append([nums[i], nums[left], nums[right]])
while left < right and nums[left] == nums[left + 1]:
left += 1
while left < right and nums[right] == nums[right - 1]:
right -= 1
left += 1
right -= 1
return res
C++
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
if (nums.size() < 3) return {};
sort(nums.begin(), nums.end());
vector<vector<int>> res;
for (int i = 0; i < nums.size() - 2; i++) {
if (nums[i] > 0) break;
if (i > 0 && nums[i] == nums[i - 1]) continue;
int left = i + 1, right = nums.size() - 1;
while (left < right) {
int tmp = nums[i] + nums[left] + nums[right];
if (tmp < 0) left++;
else if (tmp > 0) right--;
else {
res.push_back({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 res;
}
};
18 四数之和 4Sum
要点
- 由于不需要关注顺序，且需要去重，在最开始进行一次排序
- 注意剪枝时的范围，需要
nums[i] > target且nums[i] > 0才能直接 break
代码
Python
class Solution:
def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
nums.sort()
if len(nums) < 4:
return []
res = []
for i in range(len(nums) - 4):
if nums[i] > target and nums[i] > 0:
break
if i > 0 and nums[i] == nums[i - 1]:
continue
for j in range(i + 1, len(nums) - 3):
if nums[i] + nums[j] > target and nums[i] + nums[j] > 0:
break
if j > i + 1 and nums[j] == nums[j - 1]:
continue
left = j + 1
right = len(nums) - 1
while left < right:
tmp = nums[i] + nums[j] + nums[left] + nums[right]
if tmp < target:
left += 1
elif tmp > target:
right -= 1
else:
res.append([nums[i], nums[j], nums[left], nums[right]])
while left < right and nums[left] == nums[left + 1]:
left += 1
while left < right and nums[right] == nums[right - 1]:
right -= 1
left += 1
right -= 1
return res
C++
class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
if (nums.size() < 4) return {};
vector<vector<int>> res;
sort(nums.begin(), nums.end());
for (int i = 0; i < nums.size() - 3; i++) {
if (nums[i] > target && nums[i] > 0) break;
if (i > 0 && nums[i] == nums[i - 1]) continue;
for (int j = i + 1; j < nums.size() - 2; j++) {
if (nums[i] + nums[j] > target && nums[i] + nums[j] > 0) break;
if (j > i + 1 && nums[j] == nums[j - 1]) continue;
int l = j + 1, r = nums.size() - 1;
while (l < r) {
long tmp = (long) nums[i] + nums[j] + nums[l] + nums[r];
if (tmp < target) l++;
else if (tmp > target) r--;
else {
res.push_back({nums[i], nums[j], nums[l], nums[r]});
while (l < r && nums[l] == nums[l + 1]) l++;
while (l < r && nums[r] == nums[r - 1]) r--;
l++;
r--;
}
}
}
}
return res;
}
};
