Notes

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; } };

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; } };

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.size() - 1; T = 0 - nums[i]; while (l < r) { sum = nums[l] + nums[r]; if (sum == T) { res.push_back({nums[i], nums[l], nums[r]}); // Skip same numbers in each side to avoid duplicate while (l < r && nums[l] == nums[l + 1]) l++; while (l < r && nums[r] == nums[r - 1]) r--; l++; r--; } else if (sum < T) { l++; } else { r--; } } } return res; } };

tags: Two Pointers

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] != s[j]) { // remove left auto left = isPalindrome(s, i + 1, j); // remove right auto right = isPalindrome(s, i, j - 1); // return at here as we have traveled the string in the // invocation of isPalindrome. return right || left; } } return true; } private: bool isPalindrome(string & s, int i, int j) { for (; i < j; i++,j--) { if (s[i] != s[j]) { return false; } } return true; } };