# [15. 3Sum](https://leetcode.com/problems/3sum/)

## Question: (Medium)
Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.

Notice that the solution set must not contain duplicate triplets.

Example 1:

Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]
Explanation:
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0.
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0.
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0.
The distinct triplets are [-1,0,1] and [-1,-1,2].
Notice that the order of the output and the order of the triplets does not matter.
Example 2:

Input: nums = [0,1,1]
Output: []
Explanation: The only possible triplet does not sum up to 0.
Example 3:

Input: nums = [0,0,0]
Output: [[0,0,0]]
Explanation: The only possible triplet sums up to 0.
## Solution: C++

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        set<vector<int>> set_v;
        sort(nums.begin(), nums.end());
        int target=0, target2=0;
        for(int i=0; i<nums.size(); i++){
            target = 0-nums[i];
            /* implement two-sum */
            int start = i+1;
            int end = nums.size()-1;
            while(start<end){
                int temp = nums[start]+nums[end];
                if(temp>target){
                    end--;
                }
                else if(temp<target){
                    start++;
                }
                else{
                    vector<int>temp_vector = {nums[i], nums[start], nums[end]};
                    set_v.insert(temp_vector);
                    start++;
                    end--;
                }
            }
        }
        vector<vector<int>>ans;
        for(auto i=set_v.begin(); i!=set_v.end(); i++){
            ans.push_back(*i);
        }
        return ans;
    }
};

## Notes
1. We should **sort** this vector in advance.
2. using two-pointer to calculate two-sum.
3. using **C++ stl set<vector<int>>>** to solve this problem.

---

# [125. Valid Palindrome](https://leetcode.com/problems/valid-palindrome/)

## Question : (Easy)
A phrase is a palindrome if, after converting all uppercase letters into lowercase letters and removing all non-alphanumeric characters, it reads the same forward and backward. Alphanumeric characters include letters and numbers.

Given a string s, return true if it is a palindrome, or false otherwise.

Example 1:

Input: s = "A man, a plan, a canal: Panama"
Output: true
Explanation: "amanaplanacanalpanama" is a palindrome.
Example 2:

Input: s = "race a car"
Output: false
Explanation: "raceacar" is not a palindrome.
Example 3:

Input: s = " "
Output: true
Explanation: s is an empty string "" after removing non-alphanumeric characters.
Since an empty string reads the same forward and backward, it is a palindrome.
## Solution: C++

class Solution {
public:
    bool isPalindrome(string s) {
        int s_size = s.length();
        char* new_str = new char[s_size];
        int index = 0;
        for(int i=0; i<s_size; i++){
            if(s[i]==' ')
                continue;
            else if(isdigit(s[i]))
                new_str[index++]=s[i];
            else if(isalpha(s[i]))
                new_str[index++]=char(tolower(s[i]));
        }
        //cout<<new_str<<endl;
        if(index==0)
            return true;
        int start = 0;
        int end = index-1;
        while(start<end){
            if(new_str[start]!=new_str[end]){
                return false;
            }
            else{
                start++;
                end--;
            }
        }
        return true;
    }
};

## Notes
1. Using one loop to create new_str;
2. Using two-pointer to check palindrome.

---
# 1679. Max Number of K-Sum Pairs
## Question (Medium)
You are given an integer array nums and an integer k.

In one operation, you can pick two numbers from the array whose sum equals k and remove them from the array.

Return the maximum number of operations you can perform on the array.

Example 1:

Input: nums = [1,2,3,4], k = 5
Output: 2
Explanation: Starting with nums = [1,2,3,4]:
- Remove numbers 1 and 4, then nums = [2,3]
- Remove numbers 2 and 3, then nums = []
There are no more pairs that sum up to 5, hence a total of 2 operations.
Example 2:

Input: nums = [3,1,3,4,3], k = 6
Output: 1
Explanation: Starting with nums = [3,1,3,4,3]:
- Remove the first two 3's, then nums = [1,4,3]
There are no more pairs that sum up to 6, hence a total of 1 operation.
## Solution (C++)

class Solution {
public:
    int maxOperations(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end());
        int start = 0;
        int end = nums.size()-1;
        int count = 0;
        int value = 0;
        while(start<end){
            value = nums[start] + nums[end];
            if(value < k){
                start++;
            }
            else if(value > k){
                end--;
            }
            else{
                start++;
                end--;
                count++;
            }
        }
        return count;
    }
};

## Notes
* 就是two-pointer，透過nums[start]+nums[end]的數值，來決定pointer移動的方向。

## 1750. Minimum Length of String After Deleting Similar Ends

class Solution {
public:
    int minimumLength(string s) {
        int start_index = 0;
        int end_index = s.length() - 1;
        while(start_index <= end_index){
            if(start_index == end_index)
                return 1;
            char temp1 = s[start_index];
            char temp2 = s[end_index];
            if(temp1!=temp2){
                break;
            }
            else{
                while(start_index<s.length()-1 && s[start_index]==temp1){
                    start_index++;
                }
                while(end_index>0 && s[end_index]==temp2){
                    end_index--;
                }
            }
        }
        return (start_index>end_index)?0:(end_index-start_index+1);
    }
};

### Notes:
1. prefix of string: index 0~i的substring
2. suffix of string: index i~end的substring
3. 因此我們有兩個index，分別表示開頭和結尾，用tow pointer的方式來解這題
4. 若s[start_index]==s[end_index]的話表示suffix和prefix的character是一樣的
5. 但我們不知道prefix和suffix各自的長度，所以我們在更新下一次的index時，需要**考慮prefix、suffix的長度**。