运用hash表

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> hash;
        vector<int> result;
        for (int i=0; i<nums.size(); i++) {
            int numToFind = target - nums[i];
            if (hash.find(numToFind)!=hash.end()) {
                result.push_back(hash[numToFind]);
                result.push_back(i);
            }
            hash[nums[i]] = i;
        }
        return result;
    }
};

解决方法：滑动窗口方案

class Solution {
public:
    double findMaxAverage(vector<int>& nums, int k) {
        double r = INT_MIN;
        double sum = 0;
        for (int i = 0; i<nums.size(); i++) {
            if (i<k) {
                sum+=nums[i];
            }else{
                r = max(sum, r);
                sum +=nums[i]-nums[i-k];
            }
        }
        r = max(sum, r);
        return r/double(k);
    }
};

Given numRows, generate the first numRows of Pascal's triangle.

For example, given numRows = 5,
Return

class Solution {
public:
    vector<vector<int>> generate(int numRows) {
        vector<vector<int>>result(numRows);
        for (int i = 0; i<numRows; i++) {
            result[i].resize(i+1);
            result[i][0] = result[i][i] = 1;
        
            for (int j = 1; j<i; j++) {
                result[i][j] = result[i-1][j-1]+result[i-1][j];
            }
        }
        return result;
        
     }
};

Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

You may assume no duplicates in the array.

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int result = 0;
        for (int i =0; i<nums.size(); i++) {
            if (nums[i]>=target) {
                return i;
            }
        }
        return nums.size();
    }
};

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

For example, given the array[-2,1,-3,4,-1,2,1,-5,4],
the contiguous subarray [4,-1,2,1] has the largest sum = 6.

第一种解法：分治法

class Solution {
public:
    vector<int> findCrossSubArray(vector<int>& nums, int mid, int low ,int high){
        int sum = 0;
        int leftSum = INT_MIN;
        int maxLeft = 0;
        for (int i = mid; i>=low; i--) {
            sum = sum+nums[i];
            if (sum>leftSum) {
                leftSum = sum;
                maxLeft = i;
            }
        }
        sum = 0;
        int rightSum = INT_MIN;
        int maxRight = 0;
        for (int j=mid+1; j<=high; j++) {
            sum = sum+nums[j];
            if (sum>rightSum) {
                rightSum = sum;
                maxRight = j;
            }
        }
        
        return {{maxLeft,maxRight,leftSum+rightSum}};
    }

    vector<int> findMaxSubArray(vector<int>& nums,int low ,int high)
    {
        if (low==high) {
            return {{low,high,nums[low]}};
        }else{
            int mid = (low+high)/2;
            vector<int> leftSum = findMaxSubArray(nums, low, mid);
            vector<int> rightSum = findMaxSubArray(nums, mid+1, high);
            vector<int> crossSum = findCrossSubArray(nums, mid, low, high);
            if (leftSum[2]>=rightSum[2]&&leftSum[2]>=crossSum[2]) {
                return leftSum;
            }else if(rightSum[2]>=leftSum[2]&&rightSum[2]>=crossSum[2])
            {
                return rightSum;
            }
            else return crossSum;
        }
    
    }


    int maxSubArray(vector<int>& nums) {
        int len = nums.size()-1;
        vector<int> result = findMaxSubArray(nums, 0, len);
        return result[2];
    }
};

第二种解法：

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int ans=nums[0],i,j,sum=0;
        for(i=0;i<nums.size();i++){
            sum+=nums[i];
            ans=max(sum,ans);
            sum=max(sum,0);
        }
        return ans;
    }
};

Given an unsorted array of integers, find the length of longest continuous increasing subsequence.

class Solution {
public:
    int findLengthOfLCIS(vector<int>& nums) {
        int tmp = 1;
        int result = 1;
        if (nums.size()==1) {
            return tmp;
        }
        if (nums.empty()) {
            return 0;
        }
        nums.push_back(INT_MIN);
        for (int i =1; i<nums.size(); i++) {
            if (nums[i]>nums[i-1]) {
                tmp++;
            }else{
                result = max(tmp, result);
                tmp = 1;
            }
        }
        return result; 
    }
};