# 189. Rotate Array # 581. Shortest Unsorted Continuous Subarray

189. Rotate Array

Given an array, rotate the array to the right by k steps, where k is non-negative.

Example 1:

Input: [1,2,3,4,5,6,7] and k = 3
Output: [5,6,7,1,2,3,4]
Explanation:
rotate 1 steps to the right: [7,1,2,3,4,5,6]
rotate 2 steps to the right: [6,7,1,2,3,4,5]
rotate 3 steps to the right: [5,6,7,1,2,3,4]

Example 2:

Input: [-1,-100,3,99] and k = 2
Output: [3,99,-1,-100]
Explanation:
rotate 1 steps to the right: [99,-1,-100,3]
rotate 2 steps to the right: [3,99,-1,-100]

Note:

Try to come up as many solutions as you can, there are at least 3 different ways to solve this problem.
Could you do it in-place with O(1) extra space
  还没看讨论区的答案，思路就是先将数组中最后一个数字保存在temp中，再通过循环将索引为0到size()-1的元素向右移，最后将temp的值赋给v[0].

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        if(k == 0)
            return;
        for(int i = 0; i<k; i++)
        {
            int temp = nums[nums.size()-1];
            for(int i = nums.size() -1; i>0; i--)
            {
                nums[i] = nums[i-1];
            }
            nums[0] = temp;
        }
    }
};

581. Shortest Unsorted Continuous Subarray

Given an integer array, you need to find one continuous subarray that if you only sort this subarray in ascending order, then the whole array will be sorted in ascending order, too.

You need to find the shortest such subarray and output its length.

Example 1:

Input: [2, 6, 4, 8, 10, 9, 15]
Output: 5
Explanation: You need to sort [6, 4, 8, 10, 9] in ascending order to make the whole array sorted in ascending order.

Note:

Then length of the input array is in range [1, 10,000].
The input array may contain duplicates, so ascending order here means <=.

  参考了讨论区的大神思路：先定义两个标签索引变量begin = -1 与 end = -2（选择-1与-2这两个数是为了当数组中不存在非降序子列时返回 end - begin + 1==0），接着同时开始从头到尾（定义变量max表示搜索到的最大值）以及从尾到头（定义变量min表示搜索到的最小值）两个方向的搜索：
①从头到尾：当当前值比max小时（后值比前值小，不是升序），说明无序子列的end至少在当前位置。
②从尾到头：当当前值比min大时（前值比后值大，不是升序），说明无序子列的begin至少要从该位置开始

class Solution {
public:
    //参考了讨论区的最高评论答案
    int findUnsortedSubarray(vector<int>& nums) {
        int begin = -1, end = -2;
        int max = nums[0], min = nums[nums.size()-1];
        int n = nums.size();
        for(int i = 1; i<nums.size(); i++)   //向右从1到n-1，向左从n-2到0
        {
            
            if(nums[i] < max)
                end = i;
            if(nums[n-1-i] > min)
                begin = n-1-i;
            max = nums[i]>max ? nums[i]:max;
            min = nums[n-1-i]<min ? nums[n-1-i]:min;
        }
        return end - begin + 1;
    }
};

tip:
合理设置标签指针，对数组同时进行正序与倒序的搜索