相向双指针 专题一 Two Sum
- Two Sum III - Data structure design
https://leetcode.com/problems/two-sum-iii-data-structure-design/
Questions to ask:
- Are there any duplicate integers? Yes
- Is the array sorted? No
- Is it true that we gotta return true as long as we found a tuple that satisfy the requirement? Yes
解法1. List + Two pointers
Time: add:O(N)/ find: O(N)
Space: O(N)
class TwoSum {
public:
std::vector<int> arr;
TwoSum() {}
void add(int number) {
// Insertion Sort: O(N)
arr.push_back(number);
int idx = arr.size() - 1;
while (idx > 0 && arr[idx - 1] > arr[idx]){
int temp = arr[idx - 1];
arr[idx - 1] = arr[idx];
arr[idx] = temp;
idx--;
}
}
bool find(int value) {
int left = 0, right = arr.size() - 1;
while (left < right){
int sum = arr[left] + arr[right];
if (sum < value){
left++;
} else if (sum > value){
right--;
} else {
return true;
}
}
return false;
}
};
- hashmap
Time: add:O(1) find:O(N)
Space: O(N)
class TwoSum {
public:
std::unordered_map<int, int> map;
TwoSum() {
}
void add(int number) {
map[number]++;
}
bool find(int value) {
if (value <= long(INT_MIN) || value >= long(INT_MAX) ){
return false;
}
for (auto it = map.begin(); it != map.end(); it++){
//std::cout << "{" << (*it).first << ": " << (*it).second << "}\n";
int num = it->first;
int toFind = value - num;
if (toFind == num ){
// (map.count(num) >= 2 doesn't work
if (map[num] >= 2){
return true;
}
} else if (map.count(toFind) > 0) {
return true;
}
}
return false;
}
};
注意一个case, 错了好几次
input
["TwoSum","add","find"]
[[],[0],[0]]
Output
[null,null,true]
Expected
[null,null,false]
这里要注意std::unordered_map里面的count() 和[] operator还有find()的区别：
count()只能返回0或者1，也就是查询map里有没有这个key, 并不能返回有几个element是这个key(因为map的key是去重的)https://cplusplus.com/reference/map/map/count/
而[]是返回value;
map.find()是找到含有这个key的element，返回的是iterator，要得到key或者value需要it->first, it->second
3Sum
https://leetcode.com/problems/3sum/
解法一： sort + two pointer(固定一个数)
Time: O(NlogN+N^2)
Space: O(K) K is the number of answer triplets
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
std::sort(nums.begin(), nums.end());
vector<vector<int>> res;
for (int i = 0; i < nums.size() - 1; i++){
if (i > 0 && nums[i - 1] == nums[i]){
continue;
}
int target = -nums[i];
int left = i + 1, right = nums.size() - 1;
/* while (left <= right) doesn't work
* Counter example: [-1,0,1,2,-1,-4]
* Sorted: [-4,-1,-1,0,2]
* i = -4, left = 4, right = 4
* [-4,2,2]
* 原因是每一个元素只能用一次
*/
while (left < right){
if (nums[left] + nums[right] > target){
right--;
} else if (nums[left] + nums[right] < target){
left++;
} else {
res.push_back({nums[i], nums[left], nums[right]});
left++;
right--;
while (left < right && nums[left] == nums[left-1]){
left++;
}
while (left < right && nums[right] == nums[right+1]){
right--;
}
}
}
}
return res;
}
};
要特别注意为了答案去重指针略过了哪些
- Valid Triangle Number
https://leetcode.com/problems/valid-triangle-number/
class Solution {
public:
int triangleNumber(vector<int>& nums) {
if (nums.size() < 3){
return 0;
}
int ans{0};
std::sort(nums.begin(), nums.end());
// Valid triangle: num3 > num1 + num2
// Fix the max edge, use two pointers to find the other two
for (int i = 2; i < nums.size() ; i++){
int left = 0, right = i - 1;
while (left < right) {
if (nums[left] + nums[right] > nums[i]){
ans += right - left;
right--;
} else if (nums[left] + nums[right] <= nums[i]) {
left++;
}
}
}
return ans;
}
};
Time: O(NlogN + N^2 ) O(NlogN)排序，O(N^N)进行N次two sum
class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
// 1 <= nums.length <= 200
vector<vector<int>> res;
if (nums.size() < 4){
return res;
}
std::sort(nums.begin(), nums.end());
for (int i = 0; i < nums.size() -3; i++){
if (i > 0 && nums[i] == nums[i - 1]){
continue;
}
for (int j = i+1; j < nums.size() - 2; j++){
if (j != i+1 && nums[j] == nums[j - 1]){
continue;
}
int l = j + 1, r = nums.size() - 1;
while (l < r){
//[1000000000,1000000000,1000000000,1000000000]
//0
auto sum = (long long) nums[i] + nums[j] + nums[l] + nums[r];
if (sum == target){
vector<int> vect{nums[i], nums[j], nums[l], nums[r]};
res.push_back(vect);
l++;
r--;
while (l < r && nums[l] == nums[l-1]){
l++;
}
while (l < r && nums[r] == nums[r+1]){
r--;
}
} else if (sum > target) {
r--;
} else {
l++;
}
}
}
}
return res;
}
};
注意一下怎么去重的
- 4Sum II
这道题用two pointer会tle， 所以说是不能接受O(N^3)的，这个也应该在回答前跟面试官沟通清楚
class Solution {
public:
int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
// HashMap: O(N^2)
int n = nums1.size();
int count{0};
std::unordered_map<int, int> map;
for (int i = 0; i < n; i++){
for (int j = 0; j < n; j++){
int sum = nums1[i] + nums2[j];
map[sum] += 1;
}
}
for (int j = 0; j < n; j++){
for (int k = 0; k < n; k++){
int target = - (nums3[j] + nums4[k]);
count += map[target];
}
}
return count;
}
};
相向双指针 专题二 Partition 分区算法
31 · Partition Array
https://www.lintcode.com/problem/31/
class Solution {
public:
/**
* @param nums: The integer array you should partition
* @param k: An integer
* @return: The index after partition
*/
int partitionArray(vector<int> &nums, int k) {
// write your code here
int left = 0, right = nums.size() - 1;
while (left <= right){
while (left <= right && nums[left] < k){
left++;
}
while (left <= right && nums[right] >= k){
right--;
}
if (left <= right){
auto temp = nums[left];
nums[left] = nums[right];
nums[right] = temp;
}
}
return left;
// Return the partitioning index, i.e the first index i nums[i] >= k
// < k: [0, right], >= k: [left, size() - 1]
}
};
- Sort Colors
https://leetcode.com/problems/sort-colors/
class Solution {
public:
void sortColors(vector<int>& nums) {
partitionArray(nums, 1);
partitionArray(nums, 2);
}
void partitionArray(vector<int>& nums, int k){
int l = 0, r = nums.size() - 1;
while (l <= r){
while (l <= r && nums[l] < k){
l++;
}
while (l <= r && nums[r] >= k){
r--;
}
if (l <= r){
auto temp = nums[r];
nums[r] = nums[l];
nums[l] = temp;
l++;
r--;
}
}
}
};
