- tags: Algorithm
Two Pointers
Links to this note
LeetCode101: 18. 4Sum
tags: Two Pointers,Three Pointers,LeetCode101,Sorting Based on: LeetCode101: 167. Two Sum II - Input Array Is Sorted LeetCode101: 15. 3Sum We create a new loop: class Solution { public: vector<vector<int>> fourSum(vector<int>& nums, int target) { sort(nums.begin(), nums.end()); vector<vector<int>> res; int T, S, r, l; for (int i = 0; i < nums.size(); ++i) { if (i > 0 && nums[i] == nums[i - 1]) { continue; } for (int j = i + 1; j < nums....
LeetCode101: 167. Two Sum II - Input Array Is Sorted
tags: LeetCode101,Sorting,Two Pointers Key ideas: Move both sides to inwards. If the sum value less than target, move left pointer. Otherwise move right poinger. class Solution { public: vector<int> twoSum(vector<int>& numbers, int target) { int S, l = 0, r = numbers.size() - 1; vector<int> res(2, 0); while (l < r) { S = numbers[l] + numbers[r]; if (S == target) { break; } if (S < target) { l++; } else { r--; } } res[0] = l + 1; res[1] = r + 1; return res; } };
LeetCode101: 16. 3Sum Closest
tags: LeetCode101,Sorting,Two Pointers,Three Pointers Key ideas see LeetCode101: 15. 3Sum class Solution { public: int threeSumClosest(vector<int>& nums, int target) { sort(nums.begin(), nums.end()); int closest = INT_MAX, l, r, sum, T, res; for (int i = 0; i < nums.size(); i++) { l = i + 1; r = nums.size() - 1; T = target - nums[i]; while (l < r) { sum = nums[l] + nums[r]; if (abs(sum - T) < closest) { res = sum + nums[i]; closest = abs(sum - T); } if (sum == T) { return target; } if (sum < T) { l++; } else { r--; } } } return res; } };
LeetCode101: 15. 3Sum
tags: LeetCode101,Sorting,Two Pointers,Three Pointers Key ideas: Sort the nums first. Then, we travel the nums, pick current element as nums[i], and apply LeetCode101: 167. Two Sum II - Input Array Is Sorted to the remains. We skip the same numbers to avoid duplicate. class Solution { public: vector<vector<int>> threeSum(vector<int>& nums) { sort(nums.begin(), nums.end()); int l, r, sum, T; vector<vector<int>> res; for (int i = 0; i < nums.size(); i++) { // Skip same numbers to avoid duplicate if(i > 0 && nums[i] == nums[i-1]) { continue; } l = i + 1; r = nums....
Three Pointers
tags: Two Pointers
LeetCode101: 680. Valid Palindrome II
tags: String,Two Pointers,LeetCode101 Two pointers move inwards, when we meet two different characters: Remove left character to see if the remains string still satisfied a valid palindrome. Remove right character to see if the remains string still satisfied a valid palindrome. Returns true if either one above two is true. class Solution { public: bool validPalindrome(string s) { for (int i = 0, j = s.size() -1; i < j; i++,j--) { if (s[i] !...
Fast & Slow Pointers
tags: Algorithm,Two Pointers
LeetCode101: 881. Boats to Save People
tags: Hash Table,LeetCode101,Sorting,Two Pointers Intuition with HashMap class Solution { public: int numRescueBoats(vector<int>& people, int limit) { unordered_map<int, int> cntOfWeights; for (auto iter = people.begin(); iter != people.end(); ++iter) { cntOfWeights[*iter]++; } int r = 0; for (int i = 0; i < people.size(); i++) { if (cntOfWeights[people[i]] == 0) { continue; } cntOfWeights[people[i]]--; for (int j = (limit - people[i]); j > 0; --j) { if (cntOfWeights.find(j) != cntOfWeights....
LeetCode101: 11. Container With Most Water
tags: Two Pointers,Tricky,LeetCode101 The key ideas are: We start from two edges and move to the middle with two pointers. Move the pointer to the middle which side is smaller. class Solution { public: int maxArea(vector<int>& height) { int i = 0, j = height.size() - 1; int water = 0; while (i < j) { water = max(water, (j - i) * min(height[i], height[j])); if (height[i] > height[j]) { --j; } else { ++i; } } return water; } };
Differences between Sliding Window and Two Pointers
tags: Sliding Window,Two Pointers source: 力扣 LeetCode. “题解:借这个问题科普一下「滑动窗口」和「双指针」的区别 - 力扣(LeetCode).” Accessed March 11, 2022. https://leetcode-cn.com/problems/get-equal-substrings-within-budget/solution/jie-zhe-ge-wen-ti-ke-pu-yi-xia-hua-dong-6128z/. https://stackoverflow.com/a/64078338 Two Pointer to slove the problem of two elements that two pointes pointed. Sliding Window to slove the problem of all elements that in the window.