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

Given an array of integers where 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once.

Find all the elements of [1, n] inclusive that do not appear in this array.

Could you do it without extra space and in O(n) runtime? You may assume the returned list does not count as extra space.

class Solution {
public:
    vector<int> findDisappearedNumbers(vector<int>& nums) {
        int len = nums.size();
        for(int i=0; i<len; i++) {
            int m = abs(nums[i])-1;  // index start from 0
            nums[m] = nums[m]>0 ? -nums[m] : nums[m];
        }
        vector<int> res;
        for(int i = 0; i<len; i++) {
            if(nums[i] > 0) res.push_back(i+1);
        }
        return res;
    }
};

该题用了一个特殊的方法，取负法。

含义是：将元素对应的位置取负。简单一句话可能不好理解，我们举个例子。假设在位置k放了元素i，则在取负的过程中i的取值有两种可能：为正，表示当前尚未遇到元素k将该位置取负；为负，表示当前已经有元素k出现，并将元素取负。但是我们不关心k，我们关心元素i。元素i既然出现，我们就看一下位置i：为正，表示这是元素i第一次出现，我们将位置i取负；为负，表示元素i已经出现过一次，我们不做任何操作。不管一个元素出现一次还是两次，只要出现它对应的位置就会被取负。当某个元素不出现的时候，该元素对应的位置始终访问不到，所以还是正值，通过这种方法我们就可以找到哪些元素没有出现。

Given a non-empty 2D array grid of 0's and 1's, an island is a group of 1's (representing land) connected 4-directionally (horizontal or vertical.) You may assume all four edges of the grid are surrounded by water.

Find the maximum area of an island in the given 2D array. (If there is no island, the maximum area is 0.)

class Solution {
public:
    int areaNum(vector<vector<int>>& grid, int m ,int n){
        if (m<grid.size()&&m>=0&&n<grid[0].size()&&n>=0&&grid[m][n]==1) {
            //将经过的位置标记为0，避免循环检验
            grid[m][n] = 0;
            return 1+ areaNum(grid, m+1, n)+areaNum(grid, m, n+1)+areaNum(grid, m-1, n)+areaNum(grid, m, n-1);
        }
        return 0;
    }
    
    int maxAreaOfIsland(vector<vector<int>>& grid) {
        int result = 0;
        for (int i =0; i<grid.size(); i++) {
            for (int j=0; j<grid[0].size(); j++) {
                if (grid[i][j]==1) {
                    result = max(result, areaNum(grid, i, j));
                }
            }
        }
        return result;
    }
};