Given an array of integers nums, write a method that returns the "pivot" index of this array.

We define the pivot index as the index where the sum of the numbers to the left of the index is equal to the sum of the numbers to the right of the index.

If no such index exists, we should return -1. If there are multiple pivot indexes, you should return the left-most pivot index.

class Solution {
public:
    int pivotIndex(vector<int>& nums) {
        
        if(nums.empty()) return -1;
        
        int sum = 0;
        for(int i=0;i<nums.size();i++) sum+=nums[i];
    
        int leftSum = 0;
        for(int j=0;j<nums.size();j++)
        {
            if (leftSum == sum - nums[j] -leftSum) {
                return j;
        }
            leftSum += nums[j];
        }
        
        return -1;
    }
};

Say you have an array for which the \(i^{th}\) element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times). However, you may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int result = 0;
        for(int i = 1;i<prices.size();i++)
        {
            result += max(prices[i]-prices[i-1] , 0);
        }
        return result;
    }
};

Say you have an array for which the \(i^{th}\) element is the price of a given stock on day i.

If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int minPrice=INT_MAX;
        int maxProfit = 0;
        
        for (int i=0; i<prices.size(); i++) {
            minPrice = min(prices[i], minPrice);
            maxProfit = max(maxProfit, prices[i]-minPrice);
        }
        
        return maxProfit;
    }
};

Given an array of 2n integers, your task is to group these integers into n pairs of integer, say (a1, b1), (a2, b2), ..., (an, bn) which makes sum of min(ai, bi) for all i from 1 to n as large as possible.

class Solution {
public:
    int arrayPairSum(vector<int>& nums) {
        
        sort(nums.begin(),nums.end());
        int result=0;
        for (int i=0; i<nums.size(); i+=2) {
            result+=nums[i];
        }
        return result;
    }
};

Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note: The solution set must not contain duplicate triplets.

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        sort(nums.begin(),nums.end());
        vector<vector<int>> result;
        vector<int> tmpResult;
        
        int p,q,tmp;
        for(int i = 0 ;i<nums.size();i++)
        {
            if(i!=0&&nums[i]==nums[i-1]) continue;
            int currentNum = nums[i];
            p = i+1;
            q = nums.size()-1;
            
            while(p<q)
            {
                if(p!=i+1&&nums[p]==nums[p-1])
                {
                    p++;
                    continue;
                }
                tmp = nums[q]+nums[p];
                if(tmp==-currentNum)
                {
                    tmpResult.push_back(currentNum);
                    tmpResult.push_back(nums[q]);
                    tmpResult.push_back(nums[p]);
                    result.push_back(tmpResult);
                    tmpResult.clear();
                    p++;
                    q--;
                }else if (tmp>-currentNum)
                {
                    q--;
                }else p++;
            }
        }
        
        return result;
    }
};

two real problems .

• how to find the sum?
  change it to a 2 sum problem. when you have one value, the sum of the other two is -value.
  2 sum problem has a O(n) solution. so the final is O(n^2).

• how to remove the duplicate?
  for same values, we only use the first one and pass the rest.

You have a total of n coins that you want to form in a staircase shape, where every k-th row must have exactly k coins.

Given n, find the total number of full staircase rows that can be formed.

n is a non-negative integer and fits within the range of a 32-bit signed integer.

class Solution {
public:
    int arrangeCoins(int n) {
        return floor(-0.5+sqrt((double)2*n+0.25));
    }
};

这道题的主要考虑1+2+3+...+x<=n下，使x左边等式最接近n，并且不超过。

推导为：

-> 1+2+3+...+x = n
-> (1+x)x/2 = n
-> x^2+x = 2n
-> x^2+x+1/4 = 2n +1/4
-> (x+1/2)^2 = 2n +1/4
-> (x+0.5) = sqrt(2n+0.25)
-> x = -0.5 + sqrt(2n+0.25)