?-128-Longest Consecutive Sequence

1-O(n)

因为需要在O(n)的时间内完成。无法同过排序的方式实现。在此利用hash_set实现。

hash_set和hash_map是使用hash表实现，所以插入、查找、删除的时间复杂度都是O(1)。

现将所有数存储在一个hash_set中。用时O(n).

紧着对于数字a[i], 搜索a[i]+1是否在set中，若存在，继续循环搜索。

然后搜索a[i]-1是否在set中，依次递减搜索。

为了避免重复搜索。如对[1, 2, 3, 4] 搜索任一数字效果相同，所以中间做删除处理。

如果集合为空，则证明所有元素都检索完毕。

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        if(nums.size()<1)
            return 0;
        int n = nums.size();
        unordered_set<int> s;
        for(int i=0; i<n; i++)
            s.insert(nums[i]);

        int max_length = 1;
        for(int i=0; i<n; i++){
            if(s.empty())
                break;
            int current_num = nums[i], current_length=0;
            while(s.count(current_num)){
                s.erase(current_num);
                current_length++;
                current_num++;
            }

            current_num = nums[i]-1;
            while(s.count(current_num)){
                s.erase(current_num);
                current_length++;
                current_num--;
            }

            max_length = max(max_length, current_length);
        }
        return max_length;
    }
};

?2

https://discuss.leetcode.com/topic/29286/my-java-solution-using-unionfound/3

152

1.dp

http://www.qiujiawei.com/leetcode-problem-152/

class Solution {
    public int maxProduct(int[] nums) {
        int numSize = nums.length;
        int dpPreMax = nums[0];
        int dpPreMin = nums[0];
        int dpMax = nums[0];
        for(int i=1; i<numSize; i++){
            int dpCurrentMax = Math.max(dpPreMax*nums[i], dpPreMin*nums[i]);
            dpCurrentMax = Math.max(dpCurrentMax, nums[i]);
            int dpCurrentMin = Math.min(dpPreMax*nums[i], dpPreMin*nums[i]);
            dpCurrentMin = Math.min(dpCurrentMin, nums[i]);
            dpMax = dpCurrentMax > dpMax? dpCurrentMax : dpMax;
            dpPreMax = dpCurrentMax;
            dpPreMin = dpCurrentMin;
        }
        return dpMax;
    }
}

153-Find Minimum in Rotated Sorted Array

1-Binary Search

可以根据A[mid]和A[end]来判断右半数组是否sorted：

原数组：0 1 2 4 5 6 7 情况1： 6 7 0 1 2 4 5 情况2： 2 4 5 6 7 0 1

(1) A[mid] < A[end]：A[mid : end] sorted => min不在A[mid+1 : end]中

搜索A[start : mid]

(2) A[mid] > A[end]：A[start : mid] sorted且又因为该情况下A[end] min不在A[start : mid]中

搜索A[mid+1 : end]

(3) base case：

a. start = end，必然A[start]为min，为搜寻结束条件。

class Solution {
public:
    int findMin(vector<int>& nums) {
        int left = 0, right = nums.size()-1;
        while(left<right){
            int mid = left + (right -left)/2;
            if(nums[mid]<nums[right])
                right = mid;
            else
                left = mid + 1;
        }
        return nums[left];
    }
};

154-Find Minimum in Rotated Sorted Array II

Follow up for "Find Minimum in Rotated Sorted Array": What if duplicates are allowed?

Would this affect the run-time complexity? How and why?

1-???

class Solution {
public:
    int findMin(vector<int>& nums) {
        int ans = nums[0];
        for(int i=1; i<nums.size(); i++){
            ans = min(nums[i], ans);
        }
        return ans;
    }
};

2-Binary Search

In a rotate array, there will be a position where the sequence changes, no longer ascending and that number will be the minimum we are searching for. Accordingly, we can adopt binary searching to find it out and the key will be that sequence change. Let's suppose land r will be the start and the end of the array and m is the middle between them.

• First, if nums[m] > nums[r] then the sequence change number will be between m and r.
• Second, if nums[m] < nums[r], then the sequence change number will be between l and m.
• Third, if there exist duplicates and result in nums[m]==nums[r] then we will not know that that sequence change number but one thing for sure, nums[r] will not be the minimum so we can just move the r backward to eliminate nums[r] by r--, which can then be able to terminate the searching properly.

The third part is the essential, which delicately handle the duplicates and terminate the searching elegantly.

• 极端情况[1, 2, 2, 2, .....2]，nums[mid]和mums[end]一直相等，操作一直是end -= 1，所以时间复杂度变成O(n)

• 同样当A[mid] = A[end]时，无法判断min究竟在左边还是右边。

  3 1 2 3 3 3 3 3 3 3 3 1 2 3

  但可以肯定的是可以排除A[end]：因为即使min = A[end]，由于A[end] = A[mid]，排除A[end]并没有让min丢失。所以增加的条件是：

  A[mid] = A[end]：搜索A[start : end-1]

class Solution {
public:
    int findMin(vector<int>& nums) {
        int left = 0, right = nums.size()-1;
        int mid;
        while(left<right){
            mid = left + (right-left)/2;
            if(nums[mid]<nums[right])
                right = mid;
            else if(nums[mid]>nums[right])
                left = mid + 1;
            else if(nums[mid]==nums[right])
                right--;
        }
        return nums[left];
    }
};

162-Find Peak Element

1-遍历数组-O(n)

class Solution {
public:
    int findPeakElement(vector<int>& nums) {
        int n = nums.size();
        if(n==1)
            return 0;
        if(nums[0]>nums[1])
            return 0;
        if(nums[n-1]>nums[n-2])
            return n-1;
        for(int i=1; i<=n-1; i++){
            if(nums[i]>nums[i-1] && nums[i]>nums[i+1])
                return i;
        }
    }
};

2-Binary Search-O(nlgn)

• If num[i-1] < num[i] > num[i+1], then num[i] is peak

• If num[i-1] > num[i] > num[i+1], then num[0...i-1] must contains a peak

  如果不存在的话那么

  nums[-1]>nums[0]>nums[1]>....>nums[mid-1]>nums[mid].

  而nums[-1]=-$\infty $<nums[0],与已知矛盾。所以必存在peak

• If num[i-1] < num[i] < num[i+1], then num[i+1...n-1] must contains a peak

  同理

• If num[i-1] > num[i] < num[i+1], then both sides have peak, 取一个即可 (n is num.length)

class Solution {
public:
    int findPeakElement(vector<int>& nums) {
        int left = 0, right = nums.size()-1;
        while(left < right){
            int mid = left+(right-left)/2;
            if(nums[mid]<nums[mid+1])
                left = mid+1;
            else
                right = mid;
        }
        return left;
    }
};

167. Two Sum II - Input array is sorted

1-Two pointers

//30.05% 
class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        int l=0, r=numbers.size()-1; //two pointers l-left, r-right
        vector<int> ans;
        while(l<r){
            int sum = numbers[l]+numbers[r];
            if(sum==target){
                ans.push_back(l+1);
                ans.push_back(r+1);
                return ans;
            }
            else if(sum<target){
                l++;
            }
            else{
                r--;
            }
        }
    }
};

2-Binary Search

class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        for(int i=0; i<numbers.size()-1; i++){
            int left=i+1, right=numbers.size()-1, tmp=target-numbers[i];
            while(left<=right){
                int mid=(left+right)/2;
                if(numbers[mid]==tmp){
                    return vector<int> {i+1, mid+1};
                }
                else if(numbers[mid]<tmp){
                    left = mid+1;
                }
                else{
                    right = mid-1;
                }
            }
        }
    }
};

169-Majority Element

1-排序找中间值

QuickSort -> array[n/2] = O(nlogn)

TLE - Time Limit Exceeded

对于只含1, 2 的已排序数组. QuickSort因处于最坏情况而效率降低, 降至O(n^2) 造成超时.

尝试解决: 使用随机化的QuickSort.

随机化结果：AC（Beat 60%);

中间一直出现错误： conflicting types for xx 最后发现更改函数名即可。可能存在冲突

//9ms
void Swap(int* p1, int* p2){
    int tmp = *p1;
    *p1 = *p2;
    *p2 = tmp;
}
void insert_sort(int nums[], int nums_size){
    int i, j;
    int tmp;
    for(i=1; i<nums_size;i++){
        tmp = nums[i];
        for(j=i; j>0&&nums[j-1]>tmp;j--){
            nums[j]=nums[j-1];
        }
        nums[j]=tmp;
    }
}

int median_3(int a[], int left, int right){
    int center = (left+right)/2;
    if(a[left]>a[center])
        Swap(&a[left], &a[center]);
    if(a[left]>a[right])
        Swap(&a[left], &a[right]);
    if(a[center]>a[right])
        Swap(&a[center], &a[right]);
    //Now, a[left] <= a[center] <= a[right]
    Swap(&a[center], &a[right-1]); // Hide pivot
    return a[right-1]; //return pivot
}

void Qsort(int nums[], int left, int right)
{
    int i, j;
    int pivot;
    if(left+10 <=right){
        pivot = median_3(nums, left, right);
        i = left;
        j = right-1;
        for(;;){
            while(nums[++i]<pivot){}
            while(nums[--j]>pivot){}
            if(i<j){
                Swap(&nums[i], &nums[j]);
            }
            else
                break;
        }

        Swap(&nums[i], &nums[right-1]);
        Qsort(nums, left, i-1);
        Qsort(nums, i+1, right);
    }
    else{
        insert_sort(nums+left, right-left+1);
    }
}

int majorityElement(int* nums, int numsSize) {
    //insert_sort(nums, numsSize);
    Qsort(nums, 0, numsSize-1);
    return nums[numsSize/2];
}

InsertSort

AC, 但跑的慢(Beat 2%)。这个题主要是特殊样例。Insert_Sort可以很好的解决特殊样例的问题。

代码包含在上个代码中。

2-Majority Vote Algorithm

https://segmentfault.com/a/1190000004905350

需要满足Majority Element > n/2

//9ms
int majorityElement(int* nums, int numsSize) {
    int candidate, i, count=0;
    for(i=0; i<numsSize;i++){
            if(count==0){
                candidate = *(nums+i);
                count = 1;
            }
            else{
                if(candidate == *(nums+i)){
                    count ++;
                }
                else{
                    count --;
                }
            }
    }
    return candidate;
}

3-按位取众数

给定的是32位数，并且众数一定存在，那么每一位去考虑的话，对于每一位1或者0多的肯定是属于众数的。每一位相加即可知道是否是众数

//13ms
int majorityElement(int* nums, int numsSize) {
    int bitCnt[32];
    memset(bitCnt, 0, sizeof(bitCnt));

    for(int i = 0; i< numsSize; i++){
        for(int j=0; j< 32; j++){
            if(*(nums+i) & (1<<j)){
                bitCnt[j]++;
            }
        }
    }

    int ans = 0;
    for(int i = 0; i<32; i++){
        if(bitCnt[i]> numsSize/2){
            ans += (1<<i);
        }
    }
    return ans;
}

4-Hash Table

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        unordered_map<int, int> counts;
        int n = nums.size();
        for(int i=0; i<n;i++){
            if(++counts[nums[i]] > n/2)
                return nums[i];
        } 
    }
};

5-Randomization

//Really Fast!
class Solution {
public:
    int majorityElement(vector<int>& nums) {
        srand(unsigned(time(NULL)));
        int n = nums.size();
        while(1){
            int index = rand()%n;
            int candidate = nums[index];
            int cnt = 0;
            for(int j = 0; j< n; j++){
                if(candidate==nums[j]){
                    cnt ++;
                }
            }
            if(cnt>n/2)
                return candidate;
        }
    }
};

http://www.cnblogs.com/higerzhang/p/4181421.html

1. Runtime: O(n2) — Brute force solution: Check each element if it is the majority element.

2. Runtime: O(n), Space: O(n) — Hash table: Maintain a hash table of the counts of each element, then find the most common one.

3. Runtime: O(n log n) — Sorting: Find the longest contiguous identical element in the array after sorting.

4. Average runtime: O(n), Worst case runtime: Infinity — Randomization: Randomly pick an element and check if it is the majority element. If it is not, do the random pick again until you find the majority element. As the probability to pick the majority element is greater than 1/2, the expected number of attempts is < 2.

5. Runtime: O(n log n) — Divide and conquer: Divide the array into two halves, then find the majority element A in the first half and the majority element B in the second half. The global majority element must either be A or B. If A == B, then it automatically becomes the global majority element. If not, then both A and B are the candidates for the majority element, and it is suffice to check the count of occurrences for at most two candidates. The runtime complexity, T(n) = T(n/2) + 2n = O(n logn).

6. Runtime: O(n) — Moore voting algorithm: We maintain a current candidate and a counter initialized to 0. As we iterate the array, we look at the current element x: If the counter is 0, we set the current candidate to x and the counter to 1.If the counter is not 0, we increment or decrement the counter based on whether x is the current candidate.After one pass, the current candidate is the majority element. Runtime complexity = O(n).

7. Runtime: O(n) — Bit manipulation: We would need 32 iterations, each calculating the number of 1's for the ith bit of all n numbers. Since a majority must exist, therefore, either count of 1's > count of 0's or vice versa (but can never be equal). The majority number’s ith bit must be the one bit that has the greater count.

   时间复杂度: O(n2) — 蛮力法: 依次检查每一个元素是否为众数

   时间复杂度: O(n), 空间复杂度: O(n) — 哈希表: 维护一个每一个元素出现次数的哈希表, 然后找到出现次数最多的元素时间复杂度: O(n log n) — 排序: 在排序后找出连续重复出现次数最多的元素

   平均时间复杂度: O(n), 最坏复杂度: 无穷大 — 随机算法: 随机选取一个元素计算其是否为众数. 如果不是, 就重复上一步骤直到找到为止。 由于选出众数的概率 > 1 / 2, 因此期望的尝试次数 < 2

   时间复杂度: O(n log n) — 分治法: 将数组拆成2半, 然后找出前一半的众数A和后一半的众数B。则全局众数要么是A要么是B。 如果 A == B, 则它自然而然就是全局众数。 如果不是, 则A和B都是候选汇众数, 则至多只需要检查这两个元素的出现次数即可。 时间复杂度, T(n) = T(n/2) + 2n = O(n log n).

   时间复杂度: O(n) — Moore投票算法: 我们维护一个当前的候选众数和一个初始为0的计数器。遍历数组时，我们看当前的元素x:

   如果计数器是0, 我们将候选众数置为 x 并将计数器置为 1

   如果计数器非0, 我们根据x与当前的候选众数是否相等对计数器+1或者-1一趟之后, 当前的候选众数就是所求众数. 时间复杂度 = O(n).

   时间复杂度: O(n) — 位操作法: 我们需要32次迭代, 每一次计算所有n个数的第i位的1的个数。由于众数一定存在，那么或者1的个数 > 0的个数 或者反过来(但绝不会相同)。 众数的第i位一定是计数较多数字。

174-Dungeon Game

1-DP

http://bookshadow.com/weblog/2015/01/07/leetcode-dungeon-game/

为什么从右下角到左上角填充表格?

因为(0, 0)是最终的结果

class Solution {
public:
    int calculateMinimumHP(vector<vector<int>>& dungeon) {
        int m = dungeon.size(), n = dungeon[0].size();
        int dp[m][n];
        dp[m-1][n-1]=max(-dungeon[m-1][n-1]+1, 1);

        for(int i=m-2; i>=0; i--){
            dp[i][n-1] = max(dp[i+1][n-1]-dungeon[i][n-1], 1);
        }

        for(int j=n-2; j>=0; j--){
            dp[m-1][j] = max(dp[m-1][j+1]-dungeon[m-1][j], 1);
        }

        for(int i=m-2; i>=0; i--){
            for(int j=n-2; j>=0; j--){
                  // dp[i][j]+dungeon[i][j] >= min(dp[][], dp[][])
                  // dp[i][j] >=1
                dp[i][j] = max(min(dp[i+1][j], dp[i][j+1])-dungeon[i][j], 1);
            }
        }
        return dp[0][0];
    }
};

?-189-Rotate Array

1-Fail-TLE

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        int n = nums.size(), tmp;
        k = k%n;
        while(k--){
            int tmp = nums[n-1];
            for(int j=n-1; j>0; j--){
                nums[j] = nums[j-1];
            }
            nums[0]=tmp;
        }
    }
};

2-Reverse

Let the array be - 123456789 and k = 4

Step 1 - 12345 6789 ---> 54321 6789

Step 2 - 54321 6789 ---> 54321 9876

Step 3 - 543219876 ---> 678912345

Here're some exploration on why we can do the rotation by first reverse the whole array and then reverse elements from index 0 to k-1, then k to nums.length-1:

for convenience, write nums.length-->len Suppose all elements of nums[] are indexed with: 0, 1, ..., k-2. k-1, k, k+1, ..., len-2, len-1

After reversing the whole array, these elements become: len-1, len-2, ..., k+1, k, k-1, k-2, ... ,1, 0

if do this "reverse(nums, 0, k - 1)", correspondingly, we first reverse elements from first one (it's len-1 using original index) to k-1 (i.e. len-k using original index) That is , we reverse: len-1, len-2, ..., len-k, len-k-1,len-k-2,..., 1, 0 to len-k, len-k+1,...,len-2,len-1, len-k-1,len-k-2,...,1,0 |--------- k elements here---------| After "reverse(nums, k, nums.length - 1)", the nums array finally becomes: len-k, len-k+1,...len-2,len-1, 0, 1, ..., len-k-2, len-k-1 |---------- k elements---------| compared to original array: 0, 1, ..., k-2. k-1, k, k+1, ..., len-2, len-1 From the changes of these elemnents position (like 0, it may be intuitive to find the array really has been rotated by k)

//22.79%
class Solution {
public:
    void reverse(vector<int>& nums, int left,int right){
        int tmp;
        while(left<right){
            tmp =nums[left];
            nums[left++]=nums[right];
            nums[right--]=tmp;
        }
    }

    void rotate(vector<int>& nums, int k) {
        int n = nums.size();
        k%=nums.size();
        reverse(nums, 0, n-1);
        reverse(nums, 0, k-1);
        reverse(nums, k, n-1);

    }
};

3-重新开辟数组

Time complexity: O(n). Space complexity: O(n).

//53.06% 
class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        vector<int> tmp=nums;
        int new_position, n=nums.size();
        k = k%n;
        for(int i=0; i<n; i++){
            nums[(i+k)%n]=tmp[i];
        }
    }
};

*4-不理解

https://discuss.leetcode.com/topic/9801/summary-of-c-solutions

#2

#4

#5

209

1-On-双指针

class Solution {
    public int minSubArrayLen(int s, int[] nums) {
        int numsSize = nums.length;
        int ans=Integer.MAX_VALUE;
        int left=0, sum=0;
        for(int right=0; right<numsSize; right++){
            sum += nums[right];
            while(sum>=s){
                ans = Math.min(ans, right-left+1);
                sum -= nums[left++];
            }
        }
        if(ans == Integer.MAX_VALUE){
            return 0;
        }
        return ans;
    }
}

Since the given array contains only positive integers, the subarray sum can only increase by including more elements. Therefore, you don't have to include more elements once the current subarray already has a sum large enough. This gives the linear time complexity solution by maintaining a minimum window with a two indices.

O(n)的解法，我们需要定义两个指针left和right，分别记录子数组的左右的边界位置，然后我们让right向右移，直到子数组和大于等于给定值或者right达到数组末尾，此时我们更新最短距离，并且将left像右移一位，然后再sum中减去移去的值，然后重复上面的步骤，直到right到达末尾，且left到达临界位置，即要么到达边界，要么再往右移动，和就会小于给定值。

http://blog.csdn.net/lisonglisonglisong/article/details/45666975

2-Onlogn

二分搜索，sum[i] stores n0, n1, ni

sum[i] is a sorted array. and sum[j] - sum[i] >= s, we want to find the min(j-i) so that the diff >=s

so for each sum[j] >=s, sum[i]<=sum[j]-s = target, binary search sum so that find the biggest i that sum[i] <= target.

O(logN)*ON = NlogN

class Solution {
    public int binarySearch(int val, int[] nums){
        int left = 0, right = nums.length-1;
        while(left <= right){
            int mid = (right - left)/2 + left;
            if(nums[mid] > val){
                right = mid-1;
            }
            else if(nums[mid] < val){
                left = mid+1;
            }
            else{
                return mid;
            }
        }
        return right;
    }
    public int minSubArrayLen(int s, int[] nums) {
        if(nums.length < 1){
            return 0;
        }
        int numsSize = nums.length;
        int ans=Integer.MAX_VALUE;
        int left=0, right=0;
        int[] sum = new int[numsSize];
        sum[0] = nums[0];
        for(int i=1; i<numsSize; i++){
            sum[i] = sum[i-1]+nums[i];
        }
        for(int i=0; i<numsSize; i++){
            if(sum[i]>=s){
                int index = binarySearch(sum[i]-s, sum);
                ans = Math.min(ans, i-index);
            }
        }

        if(ans == Integer.MAX_VALUE){
            return 0;
        }
        return ans;
    }
}

216-Combination Sum III

1-BackTracking

REF-No.39, No.40

控制深度即可

class Solution {
public:
    void solve(vector<vector<int>>& ans, vector<int>& combination, int target, int begin_index, int cnt){
        if(cnt==0){
            if(!target)
                ans.push_back(combination);
            return;
        }
        else{
            for(int i=begin_index; i<10 && target>=i; i++){
                combination.push_back(i);
                solve(ans, combination, target-i, i+1, cnt-1);
                combination.pop_back();
            }
        }
    }
    vector<vector<int>> combinationSum3(int k, int n) {
        vector<vector<int>> ans;
        vector<int> combination;
        solve(ans, combination, n, 1, k);
        return ans;
    }
};

217-Contains Duplicate

1-Hash Table

用set或undered_set 应该更好

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

//yo
class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        unordered_set<int> my_set;
        for(int i=0; i<nums.size(); i++){
            if(my_set.find(nums[i])!=my_set.end()){
                return true;
            }
            else{
                my_set.insert(nums[i]);
            }
        }
        return false;
    }
};

2-排序

219-Contains Duplicate II

1-使用hash_map随时更新最新的映射关系。

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

2-使用set

//90.54%
class Solution {
public:
    bool containsNearbyDuplicate(vector<int>& nums, int k) {
        unordered_set<int> my_set;
        for(int i=0; i<nums.size(); i++){
            if(i>k){
                my_set.erase(nums[i-k-1]);
            }
            if(my_set.find(nums[i])!=my_set.end()){
                return true;
            }
            my_set.insert(nums[i]);
        }
        return false;
    }
};

238-

1-O(n）

我们以一个4个元素的数组为例，nums=[a1, a2, a3, a4]。 想在O(n)时间复杂度完成最终的数组输出，res=[a2a3a4, a1a3a4, a1a2a4, a2a3a4]。

比较好的解决方法是构造两个数组相乘：

1. [1, a1, a1a2, a1a2*a3]
2. [a2a3a4, a3*a4, a4, 1]

这样思路是不是清楚了很多，而且这两个数组我们是比较好构造的。

但是，上面的空间复杂度为O(N)，不满足常数时间复杂度。我们可以对上面的代码进行空间优化，用一个常数p来保存每次计算的结果值。

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        vector<int> result;
        int len = nums.size();
        int forward_product[len], backward_product[len];
        forward_product[0]=1, backward_product[len-1]=1;

        for(int i=1; i<len; i++){
            forward_product[i] = nums[i-1]*forward_product[i-1];
            backward_product[len-i-1] = nums[len-i]*backward_product[len-i];
        }

        for(int i=0; i<len; i++){
            result.push_back(forward_product[i]*backward_product[i]);
        }
        return result;
    }
};

//常数空间优化
class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        vector<int> result;
        int len = nums.size();
        int product = 1;
        result.push_back(product);
        for(int i=1; i<len ; i++){
            product *= nums[i-1];
            result.push_back(product);
        }
        product = 1;
        for(int i=len-2; i>=0; i--){
            product *= nums[i+1];
            result[i] *= product;
        }
        return result;
    }
};

?-2-

https://discuss.leetcode.com/topic/19337/my-recursive-solution-o-n-time-o-1-space/2

class Solution {
public:
    int solve(vector<int>& nums, vector<int>& result, int index, int left){
        int right=1;
        if(index < result.size()-1)
            right = solve(nums, result, index+1, left*nums[index]);
        result[index] = left*right;
        return right*nums[index];
    }
    vector<int> productExceptSelf(vector<int>& nums) {
        vector<int> result(nums.size(), 0);
        solve(nums, result, 0, 1);
        return result;
    }
};