229.Majority Element II

Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times. The algorithm should run in linear time and in O(1) space.

Hint:

How many majority elements could it possibly have?

这道题是Majority Element系列的第二题，要求O(n)的时间复杂度和O(1)的空间复杂度，题目中给出了暗示，要求先考虑一个序列中最多有多少个出现次数能超过1/3的元素，根据反证法，如果有三个符合要求的元素，那么数组的长度就不可能是n了，所以符合要求的元素最多有两个，但是最开始我并没能够从这个暗示里读出有价值的信息。

直到后来看了讨论区的答案才受到了启发，之前用过的majority voting algorithm是用来寻找出现次数过半的元素的，由于过半的元素只能有一个，所以只需要有一个count来统计投票就够了，这道题只不过是把可能符合条件的数变为2个，再加上一个count不就可以统计两个候选元素的得票状况了吗？其余步骤完全和之前相同。 代码如下：

class Solution {
public:
    vector<int> majorityElement(vector<int>& nums) {
        int curIndex1=0,curIndex2=0,count1=0,count2=0;
        int size=nums.size(),i=0,tri=size/3;
        vector<int>res;
        for(i=0;i<nums.size();i++){
            if(nums[i]==nums[curIndex1])
                count1++;
            else if(nums[i]==nums[curIndex2])
                count2++;
            else if(!count1){
                count1=1;
                curIndex1=i;
            }
            else if(!count2){
                count2=1;
                curIndex2=i;
            }
            else{
                count1--;
                count2--;
            }
        }
        count1=0;
        count2=0;
        for(i=0;i<nums.size();i++){
            if(nums[i]==nums[curIndex1])
                count1++;
            else if(nums[i]==nums[curIndex2])
                count2++;
        }
        if(count1>tri)
            res.push_back(nums[curIndex1]);
        if(count2>tri)
            res.push_back(nums[curIndex2]);
        return res;
    }
};

219.Contains Duplicate II

Given an array of integers and an integer k, find out whether there are two distinct indices i and j in the array such that nums[i] = nums[j] and the difference between i and j is at most k.

判断重复元素系列的第二题，这次不仅要找到是否存在重复元素，而且要求两元素下标之差不大于k，这个题用hash_table就比较合适了，见代码:

class Solution {
public:
    bool containsNearbyDuplicate(vector<int>& nums, int k) {
        unordered_map<int,int> hash_table;
        int i=0;
        for(i=0;i<nums.size();i++){
            if(hash_table.find(nums[i])!=hash_table.end()&&i-hash_table[nums[i]]<=k)
                return true;
            hash_table[nums[i]]=i;
        }
        return false;
    }
};

• [ TODO Contains Duplicate III]

217.Contains Duplicate I

Given an array of integers, find if the array contains any duplicates.

Your function should return true if any value appears at least twice in the array, and it should return false if every element is distinct.

判断数组中是否有重复元素系列中的第一题，最容易想到的办法是双指针法，也就是双重循环，O(n^2)的时间复杂度。不过通过排序，可以将时间复杂度降低到O(n)，代码如下:

class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        if(nums.size()==0||nums.size()==1)
            return false;
        sort(nums.begin(),nums.end());
        int i=0;
        for(i;i<nums.size();i++){
            if(nums[i]==nums[i+1])
                return true;
        }
        return false;
    }
};

这道题也可以用hash_table来完成，不过还是需要一次循环，意义不大。

209.Minimum Size Subarray Sum

Given an array of n positive integers and a positive integer s, find the minimal length of a subarray of which the sum ≥ s. If there isn’t one, return 0 instead.

For example, given the array [2,3,1,2,4,3] and s = 7, the subarray [4,3] has the minimal length under the problem constraint.

More practice: If you have figured out the O(n) solution, try coding another solution of which the time complexity is O(n log n).

求和等于给定值的最短子数组，最开始想用用双重循环把所有大于等于给定值的子数组都穷举出来然后寻找最短子数组，但是考虑到时间复杂度为O(n^2)，于是进一步考虑优化方案。

最终，在参考了讨论区之后，我打算引入滑动窗口的思想来解决问题。

初始窗口为[low,high],low,high初始值均为0，窗口内部不包含元素;因为此时窗口sum==0< s,所以上界high向右移动，直到sum大于等于s时，我们先计算长度并进行比较，之后尝试舍弃窗口的第一个元素，如果还大于等于s，则继续舍弃，直到找到和等于给定值的最短子数组。代码如下:

class Solution {
public:
    int minSubArrayLen(int s, vector<int>& nums) {
        if(nums.empty())
            return 0;
        int i=0,j=0,size=nums.size(),sum=0,min_size=INT_MAX;
        for(i=0;i<size;i++){
            while(sum<s){
                sum+=nums[++j];
            }
            min_size=min(min_size,j-i+1);
        }
        return min_size==INT_MAX ? 0:min_size;
    }
};

这里需要注意的是，虽然for循环内部还有一个while循环，但并不意味着时间复杂度为O(n^2)，因为我们考虑最坏情况，sum每加上一个nums[i]，就要进入内循环执行一次sum-=nums[low++],那么也是执行n次减法运算，总时间复杂度为O(2n)，也就是说这个算法依然是线性阶的时间复杂度。

189.Rotate Array

• [ TODO 189 use constant space to finish it] Rotate an array of n elements to the right by k steps.

For example, with n = 7 and k = 3, the array [1,2,3,4,5,6,7] is rotated to [5,6,7,1,2,3,4].

Note:

Try to come up as many solutions as you can, there are at least 3 different ways to solve this problem.

旋转数组，旋转方法就是不断向右移动元素，末尾移至开头。暂时只成功了通过复制新数组进而将合适的元素填入原数组这一种方法，time complexity,space complexity均为O(n)，原理见代码:

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