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;
    }
};

class Solution {
public:
    int maximumProduct(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int len = nums.size();
        int tmp1 = nums[len-1]*nums[len-2]*nums[len-3];
        int tmp2 = nums[len-1]*nums[0]*nums[1];
        return max(tmp1, tmp2);
    }
};

主要考虑含有负数的情况。

Given an array of integers that is already sorted in ascending order, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.

You may assume that each input would have exactly one solution and you may not use the same element twice.

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

Given a sorted integer array without duplicates, return the summary of its ranges.求数组中，连续数字的区间。

class Solution {
public:
    vector<string> summaryRanges(vector<int>& nums) {
        
        vector<string> result;
        if(nums.size()==0) return result;
        
        int end = nums[0]+1;
        int total = 0;
        if (nums.size()==1) {
            result.push_back(to_string(nums[0]));
            return result;
        }
        nums.push_back(INT_MAX); //充当哨兵
        for (int i=1; i<nums.size(); i++) {
            if (nums[i]==end) {
                end++;
                total++;
                continue;
            }else{
                end = nums[i]+1;
                if (total==0) {
                    result.push_back(to_string(nums[i-1]));
                }else{
                    string tmp = to_string(nums[i-1-total])+"->"+to_string(nums[i-1]);
                    result.push_back(tmp);
                }
                total = 0;
            }
        }
        return result;
    }
};

Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.

You may assume that the array is non-empty and the majority element always exist in the array.

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int total = 1;
        int tmp = 1;
        int result = nums[0];
        if (nums.size()==1) {
            return result;
        }
        nums.push_back(INT_MAX); //在最后增加一个边界哨兵
        for (int i=1; i<=nums.size(); i++) {
            if (nums[i]==nums[i-1]) {
                tmp++;
            }else{
                result = tmp>total ? nums[i-1]:result;
                total = max(tmp, total);
                tmp = 1;
            }
        }
        
        return result;
    }
};