2020-03-19 刷题1（三数之和）

15 三数之和

这种解法真的是非常机智啊。因为这个算法的时间复杂度不会小于O(n^2)了，首先对数组进行排序，只会带来O(nlogn)的代价，可以接受。
这个问题最难的地方在于，如何保证三元组不重复，而采用双指针的做法，就可以保证我们添加到ret数组中的三元组的三个元素是单调增的，并且添加顺序也是按照前两个元素严格递增顺序添加的，不会出现（-1， 0， 1）和（-1，1， 0）这种情况。
如果采用哈希表，设置两层循环，去重会变得很困难，还是双指针比较简单明了，学习了。

这个是我参考的一个题解，讲得非常好。

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> ret;
        if(nums.size() < 3) return ret;
        sort(nums.begin(), nums.end());
        for(int i = 0; i < nums.size() - 2; i++){
            if(nums[i] > 0) break;
            if(i > 0 && nums[i] == nums[i - 1])
                continue;
            int l = i + 1, r = nums.size() - 1;
            int two_sum = 0 - nums[i];
            while(l < r){
                // skip repeat element
                while(l > i + 1 && l < r && nums[l] == nums[l - 1])
                    l++;
                while(r < nums.size() - 1 && l < r && nums[r] == nums[r + 1])
                    r--;
                while(l < r && nums[l] + nums[r] < two_sum)
                    l++;
                while(l < r && nums[l] + nums[r] > two_sum)
                    r--;
                if(l < r && nums[l] + nums[r] == two_sum){
                    ret.push_back({nums[i], nums[l], nums[r]});
                    l++;
                    r--;
                }
            }
        }
        return ret;
    }   
};

409 最长回文串

很简单的哈希表+字符串题

class Solution {
public:
    int longestPalindrome(string s) {
        map<char, int> cmap;
        for(int i = 0;  i < s.size(); i++){
            cmap[s[i]]++;
        }
        map<char, int>::iterator iter;
        bool single_flat = false;
        int len = 0;
        for(iter = cmap.begin(); iter != cmap.end(); iter++){
            len += iter->second / 2 * 2;
            if(!single_flat && iter->second % 2){
                len++;
                single_flat = true;
            }
        }
        return len;
    }
};