11. 盛最多水的容器-双指针的应用

这道题用两个for然后剪枝可以通过，但是思路不行。

https://leetcode-cn.com/problems/container-with-most-water/

可以使用双指针来解答

class Solution {
public:
    int maxArea(vector<int>& height) {
        int Max_capacity = -1;
        int left = 0 , right = height.size()-1;
        while(left != right){
            int capacity = min(height[left] , height[right]) * (right - left);
            if(Max_capacity < capacity) Max_capacity = capacity;
            height[left] < height[right] ? (++left) : (--right);
        }
        return Max_capacity;
    }
};

正确性证明：

capacity = min(h[left] , h[right]) * (right - left)，我们假设h[left] < h[right]，如果我们向左移动right，那么capacity只会减小，这样没法找到最大值，而向右移动left，capacity可能增大也可能减小。
一开始left和right分别指向容器的最左端和最右端，如果用暴力来求的话，[left , right]范围内一定可以找到Max_capacity，还是假设h[left] < h[right]，left++相当于减少了(left , right-1)、(left , right-2)……这些值都<(left , right)，所以我们每一步所丢失的解都不会影响当前解空间内的最大值（要么是min(h[left] , h[right]) * (right - left)，要么在[left-1 , right]的解空间内）。

1. 两数之和

这道题用暴力也可以过，但是这显然不是好的方法。

https://leetcode-cn.com/problems/two-sum/

multimap+双指针

首先我们使用multimap记录数据的index，因为map是排好序的，所以我们可以用双指针来缩小查找范围。

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        multimap<int , int> mp;
        for(int i = 0 ; i<nums.size() ; ++i){
            mp.insert(pair<int , int>(nums[i] , i));
        }
        auto left = mp.begin() , right = --mp.end();
        while(left != right){
            if(left->first + right->first == target){
                return {left->second , right->second};
            }
            else if(left->first + right->first < target){
                left++;
            }
            else right--;
        }
        return {};
    }
};

unordered_map（哈希表的应用）

unordered_map的实现是基于哈希表，所以其查找很快，所以最终是无序的。由于这道题每个测试样例只有一个答案，所以用map虽然会覆盖重复元素，但是可以找到解。

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {

        unordered_map<int,int> m;

        for(int i=0;i<nums.size();i++){
            m[nums[i]] = i;
        }
        for(int i=0;i<nums.size();i++)
        {
            if(m.find(target-nums[i]) != m.end() && m[target-nums[i]] != i){
                return {i , m[target-nums[i]]};
            }
        }
        return {};
    }
};

466. 统计重复个数-循环节（好难）

https://leetcode-cn.com/problems/count-the-repetitions/

我们可以把这道题转成：n1个s1中可以找出多少个s2(个数向下取整)，然后除以n2就是答案了，所以关键是求有多少个s2，但是n1可以很大，所以遍历n1个s1肯定不行。

再想，我们可以求出x个s1中有y个s2，其中x和y都是整数，但是这样不能保证y是整数，由于s1和s2是循环出现的，所以1个s2占多少s2都是固定的，所以很多情况下找不出这样的y。

有没有一种方法可以实现x个s1中有y个s2，其中x和y都是整数呢？我们可以这样想，如果此题有解，那么s1中必定包含s2中所有种类的元素，只不过顺序是不同的，比如说s1 = ‘abaacdbac’，s2 = ‘adcbda’，第一次只能有’abc’，第二次为’bda’。那么是否存在一个x，使得x个s1中找到s2的一段循环节，即从x开始遍历s2而不是从s2[0]开始遍历。我们考虑每次遍历s1时第一个s2元素，比如下图中的b,d,b,d，我们假设为x，那么x只能取s2中的任意一个元素，如果有两次x重复了，那么接下来的工作就和上一次一样了，因为相当于循环节和s1同步了，这样就找到了循环节了。

正确性证明

x一定会有重复，根据鸽巢原理，x的取值是有限的。
循环节里一定包含的是整数个s2，因为我们可以认为是从s2中x元素开始对应，经过几个s1的遍历后，又以x元素结束，此时一定是整数个s2

其实循环节就是换一种方式求出x个s1中有y个s2，其中x和y都是整数。

class Solution {
public:
    int getMaxRepetitions(string s1, int n1, string s2, int n2) {
        if(n1 == 0) return 0;
        int index = 0 , sum_s1 = 0 , sum_s2 = 0;    //index表示当前对应的是s2中的第几个元素，sum_s1和sum_s2表示s1经过sum_s1次遍历后，所包含的完整的sum_s2个s2(此时可能还包含不完整的s2，向下取整)
        unordered_map<int , pair<int , int> > mp;
        pair<int , int> pre , in;
        while(1){
            ++sum_s1;
            for(auto ch : s1){
                if(ch == s2[index]){
                    ++index;
                    if(index == s2.size()){
                        index = 0;
                        sum_s2++;
                    }
                }
            }
            if(sum_s1 == n1){  //未找到循环节
                return sum_s2 / n2;
            }

            if(mp.count(index)){  //找到了循环节
                pre = mp[index];
                int sum_s1_prime = pre.first;
                int sum_s2_prime = pre.second;
                in = {sum_s1 - sum_s1_prime , sum_s2 - sum_s2_prime};  //一个循环节中包含（sum_s1 - sum_s1_prime）个s1，包含(sum_s2 - sum_s2_prime)个s2
                break;
            }
            else {
                mp[index] = {sum_s1 , sum_s2};  //用哈希表存
            }
        }
        int sum = pre.second + (n1 - pre.first) / in.first * in.second;   //循环节中s2的个数 + 一开始未进入循环节中s2的个数
        int rest = (n1 - pre.first) % in.first;     //不够一个循环节的s1个数
        for(int i = 0 ; i<rest ; ++i){
            for(auto ch : s1){
                if(ch == s2[index]){
                    index++;
                    if(index == s2.size()){
                        sum++;
                        index = 0;
                    }
                }
            }
        }
        return sum / n2;
    }
};

4. 寻找两个有序数组的中位数-二分法

https://leetcode-cn.com/problems/median-of-two-sorted-arrays/

此题要求复杂度为o(log(n+m))，所以合并是o((n+m)/2)，不符合要求，要用二分法来查找。

一开始根本没想到用二分，看了官方题解才知道是这样的思路。

如图，我们可以考虑有一条分割线把A和B分开，使得：

如果n+m是奇数，那么left_part部分的总长度 = right_part部分的总长度+1；
如果n+m是偶数，那么left_part部分的总长度 = right_part部分的总长度；
A[i-1] <= B[j]，B[j-1] <= A[i]

第三点如果成立了，那么说明left_part部分的所有数都小于right_part部分的所有数，而一二点保证了两边的数的个数相同，那么此时中位数不就找到了吗？

如果n+m是奇数，由于left_part部分的总长度 = right_part部分的总长度+1，所以中位数一定是left_part中最大的数，即result = max{A[i-1] , B[j-1]}；
如果n+m是偶数，由于left_part部分的总长度 = right_part部分的总长度，所以一个数在left_part中，一个在right_part中，即result = (max{A[i-1] , B[j-1]} + min{A[i] + B[j]} )/2

当然，我们可以让i从0开始到n结束一个一个找，但是时间不允许，现在的问题是从[0 , n]中找到i，所以用二分法来找，用二分法就必须确定边界，即i的查找边界，我们可以把left_part部分的总长度设为k，由图可知，i+j = k（0<=i<=n），但是我们要保证0<=j<=m，所以我们就可以确定i的范围[max(0 , k-m) , min(n , k)]，有了范围后，还得确定二分法的内容：

如果A[i-1] <= B[j]，B[j-1] <= A[i]，那么就可以break了
如果A[i-1] > B[j]，那么说明A[i-1]太大，需要减小i，所以right = mid - 1
如果B[j-1] > A[i]，那么说明A[i]太小，需要增加i，所以left = mid + 1

最后要注意边界值的问题：j = 0时，j-1会是负数，j = m时，j是不合法的值，但是这样的情况是存在的，需要特殊处理。

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {

        int n = nums1.size();
        int m = nums2.size();
        if(n == 0){
            if(m%2) return nums2[m/2];
            else {
                return (double(nums2[m/2]) + double(nums2[m/2-1]))/2;
            }
        }
        if(m == 0){
            if(n%2) return nums1[n/2];
            else {
                return (double(nums1[n/2]) + double(nums1[n/2-1]))/2;
            }
        }

        int k;
        if((n + m) % 2){
            k = (n + m)/2 + 1;
        }
        else {
            k = (n + m)/2 ;
        }
        int left = max(0 , k-m) , right = min(k , n);
        int result;
        int a , b , c , d;
        while(left <= right){
            int mid = (left + right) / 2;
            int mid1 = k - mid;
            //特殊值的处理
            if(mid-1 >= 0){
                a = nums1[mid-1];
            }
            else a = min(nums1[0] , nums2[0]);
            if(mid1-1 >=0){
                b = nums2[mid1-1];
            }
            else b = min(nums1[0] , nums2[0]);
            if(mid < n){
                c = nums1[mid];
            }
            else c = max(nums1[n-1] , nums2[m-1]);
            if(mid1 < m){
                d = nums2[mid1];
            }
            else d = max(nums1[n-1] , nums2[m-1]);

            if( a <= d && b <= c){
                result = mid;
                break;
            }
            else if(b > c){
                left = mid + 1;
            }
            else if(a > d){
                right = mid - 1;
            }
        }
        if((n + m) % 2){
            return max(a , b);
        }
        else {
            return (double(max(a , b)) + double(min(c , d))) / 2.0;
        }
    }
};

3. 无重复字符的最长子串-优化的滑动窗口

https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/

我们可以将一段没有重复字符的字符串想成一个滑动窗口，用哈希表记录上一次遇见字符的下标，如果此字符在滑动窗口中出现过，那么更新滑动窗口的开始位置。窗口的左端走的慢，右端走的快，窗口只能向前运动，不能向后运动。

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        if(s.size() == 0) return 0;
        int Max_sum = -1 , sum = 0;
        unordered_map<char , int> mp;
        int i = 0 , j = 0;   //i是左端，j是右端
        for(j ; j<s.size() ; ++j){
            if( !mp.count(s[j]) || mp[s[j]] < i){  //如果以前没有出现过 或者是 出现过但是当前窗口中没有此字符
                Max_sum = max(Max_sum , j-i+1);
            }
            else i = mp[s[j]] + 1;
            mp[s[j]] = j;
        }
        return Max_sum;
    }
};

5. 最长回文子串

https://leetcode-cn.com/problems/longest-palindromic-substring/

解法1：动态规划

动态规划的题不熟，几乎遇见动态规划就不会做了。。。

首先要说的是暴力法，就是遍历每个子串，然后判断是不是回文串，但是这样会有很大的字符串是没必要判断的，比如说’babac’，判断’babac’时，’aba’已经是回文串了，那么’babac’肯定不是回文串，而无需再用常规方法来判断其是否为回文串，即暴力法最大的问题在于判断是否为回文串的这一环节上浪费了时间。时间效率是O(n^3）。

动态规划法就解决了这一问题，我们设dp[j][i]表示从j到i的字符子串，那么dp[j][i]是回文串 <=> (dp[j+1][i-1] == 1 and s[j] == s[i])，即判断一个字符子串是否为回文串仅需判断他的子串是否为回文串。

class Solution {
public:
    string longestPalindrome(string s) {
        int len = s.size();
        if(len <= 1) return s;
        vector<vector<int> > dp(len , vector<int>(len , 0));
        for(int i = 0 ; i<len ; ++i){
            dp[i][i] = 1;   //一个字符的子串一定是回文串
        }
        int start = 0 , sum = -1;  //定义结果的开始字符index和子串的最大长度
        for(int i = 1 ; i<len ; ++i){
            for(int j = 0 ; j<i ; ++j){
                if(s[j] == s[i]){
                    if(i == j+1){
                        dp[j][i] = 1;
                    }
                    else dp[j][i] = dp[j+1][i-1];
                }
                else dp[j][i] = 0;

                if(dp[j][i]){
                    if(sum < i-j+1){
                        sum = i-j+1;
                        start = j;
                    }
                }
            }
        }
        return s.substr(start , sum);
    }
};

由双重for循环得知，遍历了所有的子串。效率是O(n^2)，虽然遍历了所有子串，但是在判断是否是回文串这一环节中提高了效率。

解法二：中心拓展法

这一解法思想很简单，效率也比dp高一点。思路就是回文串是对称的，所以一定有中心点，中心点可以是一个字符，也可以是两个字符，一个字符的中心点有n个，两个字符的中心点有n-1个，所以一共有2n-1个中心点，然后在中心点的基础上左右两边同时进行拓展。

class Solution {
public:
    string longestPalindrome(string s) {
        int len = s.size();
        int start = 0 , Max_length = 1;
        for(int i = 0 ; i<len ; ++i){
            int l1 = get_palindromic_substring(s , i , i);
            int l2 = get_palindromic_substring(s , i , i+1);
            if(Max_length < max(l1 , l2)){
                Max_length = max(l1 , l2);
                start = i - (Max_length - 1) / 2;
            }
        }
        return s.substr(start , Max_length);
    }
    int get_palindromic_substring(string &s , int left , int right){
        while(left >= 0 && right < s.size() && s[left] == s[right]){
            --left;
            ++right;
        }
        return right - left - 1;
    }
};

注意代码中函数get_palindromic_substring中第一个参数使用了引用，这样使得在每次调用函数时，不用复制字符串。其实用const string & 更好。时间效率是O(n^2)。