快速幂、滑动窗口

快速幂

通常关于快速幂的问题就是求x的n次方（不考虑大数），如果我们使用最简单的循环：

for(int ans = 1,i <= n; i++){
        ans *=x;
    }

它的时间复杂度就是o(n)，但是通常这样的题都会要求时间复杂度低于o(n)，那么我们就需要来优化这个代码。

首先我们假设x = 3，n = 10。

ans = 3^ 10 = (3 ^ 2) ^ 5

此时我们发现循环次数已经变为了原来的1/2，但是幂已经变成了奇数，对于奇数，我们还有继续优化的空间，所以我们可以将式子改写为

ans = (9 ^ 1) (9 ^ 4) = 9 (81 ^ 2) = 9 * 6561

所以 ans = 3^ 10 = (3 ^ 2) ^ 5 = (9 ^ 1) (9 ^ 4) = 9 (81 ^ 2) = 9 * 6561

用代码来表示则是

while(n > 0){
        if(n % 2 == 0){
            n /= 2;
            x *= x;
        }else{
            n = (n - 1) / 2;
            ans *= x;
            n /= 2;
            x *= x;
        }
    }

但是这段代码还有继续优化的空间。在之前的位运算中提到

1 & 1 = 1， 1 & 0 = 0

如果一个数是奇数，那么它的二进制表达式最后一位一定是1，反之则为0。

而且除以2可以用位运算右移1位则会变为原来的一半。

最后优化完的代码如下

while(n > 0){
        if((n & 1) == 1){
            ans *= x;
        }
        x *= x;
        n >>= 1;
    }

剑指Offer16

实现 pow(x, n) ，即计算 x 的 n 次幂函数（即，xn）。不得使用库函数，同时不需要考虑大数问题。
-100.0 < x < 100.0
-2^31 <= n <= 2^31-1
-10^4 <= xn <= 10^4

代码如下：

class Solution {
public:
    double myPow(double x, int n) {
        if(n == 0 || x == 1){
            return 1;
        }
        long b = n;
        if( b < 0){
            b = -b;
            x = 1 / x;
        }
        double ans = 1.00;
        while(b > 0){
            if((b & 1) == 1){
                ans *= x;
            }
            x *= x;
            b >>= 1;
        }
        return ans;
    }
};

滑动窗口

滑动窗口一般是用在数组当中的一种思想，这里我们直接配合例题来介绍。

剑指Offer48

请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。
输入: "abcabcbb"
输出: 3
0 <= s.length <= 5 * 104`
s 由英文字母、数字、符号和空格组成

首先我们能直接想到的就是找出它所有的字符串，然后便利有没有重复元素，从而确定它的最长子字符串，这样的方法的时间复杂度为o(n ^ 3)，这肯定不是我们需要的算法。但是我们可以运用滑动窗口来解决这个问题。

首先我们设定left = 0, right = 0，left不动，right持续+1，直到窗口里面有了一个重复的元素为止，当出现了重复元素时left持续+1，直到越过了right所指向的重复元素为止，不断的记录窗口的长度，从而得到最长字串的长度。

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int ans = 0, right = 0, left = 0;
        vector<bool> hash(256, false);
        while(right < s.size()){
            while(hash[s[right]]){
                hash[s[left++]] = false;
            }
            ans = max(ans, right - left + 1);
            hash[s[right++]] = true;
        }
        return ans;
    }
};

但是我们还有继续优化的空间。如果重复字符在窗口中间，要越过重复数字，则需要非常多的left+1，那么我们可以选择直接让left直接移动到重复元素的后面。

我们要记录在滑动的过程中每个元素出现的位置，当重复元素出现时，只要重复元素之前出现的那个位置大于等于窗口左边界的下标，就可以直接跳过，反之则不移动左边界。

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int ans = 0, right = 0, left = 0;
        vector<int> value(128,-1);
        while(right < s.size()){
            if(value[s[right]] != -1){
                left = max(left,value[s[right]] + 1);
            }
            value[s[right]] = right;
            ans = max(ans , right - left + 1);
            right++;
        }
        return ans;
    }
};

剑指Offer57-2

输入一个正整数 target ，输出所有和为 target 的连续正整数序列（至少含有两个数）。
序列内的数字由小到大排列，不同序列按照首个数字从小到大排列
输入：target = 9
输出：[[2,3,4],[4,5]]

思路：首先我们需要，因为至少含有两个数，所以我们的左边界最大值小于等于target / 2，确立了我们左边界的范围后，我们只需要确定不同情况下的滑动方向即可。

当窗口和小于target时，我们需要右边界右移

当窗口和大于target时，我们需要左边界右移

当窗口和等于target时，我们需要左边界右移寻找下一个解

代码如下：

class Solution {
public:
    vector<vector<int>> findContinuousSequence(int target) {
        int right = 1 , left = 1, sum = 0;
        vector<vector<int>> ans;
        while(left <= target / 2){
                if(sum < target){
                    sum += right;
                    right++;
                } 
                else if (sum > target){
                    sum -= left;
                    left++;
                }else{
                    vector<int> arr;
                    for(int k = left; k < right; k++){
                        arr.push_back(k);
                    }
                    ans.push_back(arr);
                    sum -= left;
                    left++;
                }
        }
        return ans;
    }
};