求给定排序数列中的指定和

我们可以使用 两数之和 的解法在 O( n²) 时间 O( 1 ) 空间暴力解决，也可以用哈希表在 O( n ) 时间和 O( n ) 空间内解决。然而，这两种方法都没有用到输入数组已经排序的性质，我们可以做得更好。

我们使用两个指针，初始分别位于第一个元素和最后一个元素位置，比较这两个元素之和与目标值的大小。如果和等于目标值，我们发现了这个唯一解。如果比目标值小，我们将较小元素指针增加一。如果比目标值大，我们将较大指针减小一。移动指针后重复上述比较知道找到答案。

假设 [...,a,b,c,...,d,e,f,…] 是已经升序排列的输入数组，并且元素 b,e 是唯一解。因为我们从左到右移动较小指针，从右到左移动较大指针，总有某个时刻存在一个指针移动到 b 或e 的位置。不妨假设小指针县移动到了元素 b ，这是两个元素的和一定比目标值大，根据我们的算法，我们会向左移动较大指针直至获得结果。

class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        int low = 0, high = numbers.size() - 1;
        while (low < high) {
            int sum = numbers[low] + numbers[high];
            if (sum == target)
                return {low + 1, high + 1};
            else if (sum < target)
                ++low;
            else
                --high;
        }
        return {-1, -1};
    }
};

是否需要考虑 numbers[low] + numbers[high] 溢出呢？答案是不需要。因为即使两个元素之和溢出了，因为只存在唯一解，所以一定会先访问到答案。

复杂度分析

• 时间复杂度：O( n )。每个元素最多被访问一次，共有 n 个元素。
• 空间复杂度：O( 1 )。只是用了两个指针。

旋转数组

1 - 暴力：

最简单的方法是旋转 k 次，每次将数组旋转 1 个元素。

2 - 使用额外的数组：

我们可以用一个额外的数组来将每个元素放到正确的位置上，也就是原本数组里下标为 i 的我们把它放到 (i+k)%数组长度 的位置。然后把新的数组拷贝到原数组中。

3 - 使用环状替换：

public class Solution {
    public void rotate(int[] nums, int k) {
        k = k % nums.length;
        int count = 0;
        for (int start = 0; count < nums.length; start++) {
            int current = start;
            int prev = nums[start];
            do {
                int next = (current + k) % nums.length;
                int temp = nums[next];
                nums[next] = prev;
                prev = temp;
                current = next;
                count++;
            } while (start != current);
        }
    }
}

复杂度分析

• 时间复杂度：O( n ) 。只遍历了每个元素一次。
• 空间复杂度：O( 1 ) 。使用了常数个额外空间。

4 - 使用反转

这个方法基于这个事实：当我们旋转数组 k 次， k % n 个尾部元素会被移动到头部，剩下的元素会被向后移动。
在这个方法中，我们首先将所有元素反转。然后反转前 k 个元素，再反转后面 n − k 个元素，就能得到想要的结果。
假设 n = 7 且 k = 3 。

原始数组                  : 1 2 3 4 5 6 7
反转所有数字后             : 7 6 5 4 3 2 1
反转前 k 个数字后          : 5 6 7 4 3 2 1
反转后 n-k 个数字后        : 5 6 7 1 2 3 4 --> 结果

public class Solution {
    public void rotate(int[] nums, int k) {
        k %= nums.length;
        reverse(nums, 0, nums.length - 1);
        reverse(nums, 0, k - 1);
        reverse(nums, k, nums.length - 1);
    }
    public void reverse(int[] nums, int start, int end) {
        while (start < end) {
            int temp = nums[start];
            nums[start] = nums[end];
            nums[end] = temp;
            start++;
            end--;
        }
    }
}

复杂度分析

• 时间复杂度：O( n ) 。 n 个元素被反转了总共 3 次。
• 空间复杂度：O( 1 ) 。 没有使用额外的空间。

求和

按位进行逻辑运算：

int getSum(int a, int b) {
    int c = a ^ b;
    unsigned int d = a & b;
    if(d != 0 ) {
        //说明存在进位
        d <<= 1;
        return getSum(c ,d);
    }
    else
        return c;
}

二叉树的中序遍历

二叉搜索树用中序遍历始终可以得到一个有序数组

中序遍历（LDR）是 二叉树遍历 的一种，也叫做 中根遍历 、中序周游。在二叉树中，中序遍历首先遍历左子树，然后访问根结点，最后遍历右子树。

中序遍历首先遍历左子树，然后访问根结点，最后遍历右子树。若 二叉树 为空则结束返回，否则：

typedef struct TreeNode {
    int data;
    struct TreeNode *left;
    struct TreeNode *right;
    struct TreeNode *parent;
} TreeNode;

void middle_order(TreeNode* Node) {
    if(Node != NULL) {
        middle_order(Node->left);
        printf("%d ", Node->data);
        middle_order(Node->right);
    }
}

调用时：middle_order(Root); //Root为树的根