nSum系列题目总结

超、凢脫俗 2022-06-08 11:28 162阅读 0赞

**1、Two Sum**

**原题地址：**[https://leetcode.com/problems/two-sum/description/][https_leetcode.com_problems_two-sum_description]

**题目描述：**

Given an array of integers, return **indices** of the two numbers such that they add up to a specific target.

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

**Example:**

Given nums = \[2, 7, 11, 15\], target = 9,

Because nums\[**0**\] + nums\[**1**\] = 2 + 7 = 9,

return \[**0**,**1**\].

**思路**：设置一个哈希表用来存储元素num及下标，这样可以在o(1)的时候复杂度里面查找到target-num这个元素是否存在。如果存在是接返回两个元素的下标即可。

**AC代码：**

vector<int> twoSum(vector<int> &numbers, int target)
    {
        //Key is the number and value is its index in the vector.
            unordered_map<int, int> hash;
            vector<int> result;
            for (int i = 0; i < numbers.size(); i++) {
                    int numberToFind = target - numbers[i];
    
                    //如果numberToFind在哈希表中存在，直接返回两个数的下标
                    if (hash.find(numberToFind) != hash.end()) {
                        //+1 because indices are NOT zero based
                            result.push_back(hash[numberToFind] + 1);
                            result.push_back(i + 1);                 
                            return result;
                    }
    
                    //如果不在哈希表中，则将当前元素放入哈希表中
                    hash[numbers[i]] = i;
            }
            return result;
    }

**（2）3sum**

**原题地址**：[https://leetcode.com/problems/3sum/description/][https_leetcode.com_problems_3sum_description]

**题目描述**：

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.

For example, given array S = \[-1, 0, 1, 2, -1, -4\],

A solution set is:

\[-1, 0, 1\],

\[-1, -1, 2\]

**思路：**引用上一题的思路，在遍历到元素num的时候，相当于求后两个元素是否能组成和为-num。但是会出现重复元素的情况，因此需要先排序。

先固定第一个元素first，然后second指向下一个元素，third指向最后一个元素，找出second+third=-first的情况

*----------------------------------------------------*

^ ^ ^

| | |

| +- second third

\+-first

如果*nums\[first\] + nums\[second\] + nums\[third\]* < *0*, 这是需要增大sum，所以second++

*----------------------------------------------------*

^ ^ ^

| | |

| +- second third

\+-first

如果sum > target，即*nums\[first\] + nums\[second\] + nums\[third\]* >0，third--。

如果sum = target，直接存起来当前的结果

*----------------------------------------------------*

^ ^ ^

| | |

| +- second third

\+-first

循环的条件是second<third

\----------------------------------------------------

^ ^ ^

| |

\+- second third

\+-first

结束条件first=len-3, second = len-2, third = len-1

*----------------------------------------------------*

^ ^ ^

| | \`- third

| +- second

\+-first

**AC代码：**

class Solution {
    public:
        vector<vector<int>> threeSum(vector<int>& nums) {
            int len = nums.size();
            vector<vector<int> > res;
            sort(nums.begin(), nums.end());
            for(int index = 0;index < len;index++){
                int target = -nums[index];
                int front = index+1;
                int back = len-1;
                while(front < back){
                    int sum = nums[front] + nums[back];
                    if(sum < target){
                        front++;
                    }else if(sum > target){
                        back--;
                    }else{
                        vector<int> triplet(3, 0);
                        triplet[0] = nums[index];
                        triplet[1] = nums[front];
                        triplet[2] = nums[back];
                        res.push_back(triplet);
                        
                        while(front < back && nums[front] == triplet[1])    
                            front++;
                        
                        while(front < back && nums[back] == triplet[2]) 
                            back--;
                    }
                }//while
                while(index+1 < len && nums[index+1] == nums[index]){
                    index++;
                }
            }//for
            return res;
        }
    };

**（3）3Sum Closest**

**原题地址**：[https://leetcode.com/problems/3sum-closest/description/][https_leetcode.com_problems_3sum-closest_description]

**题目描述：**

Given an array *S* of *n* integers, find three integers in *S* such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution.

For example, given array S = \{-1 2 1 -4\}, and target = 1.

The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

**思路：**

前面和上一题思路一样，只是在算的过程中存一下差diff，每算出来一个结果的时候和diff进行比较，如果比diff还小，用当前结果覆盖之前算出来的结果

**AC代码：**

class Solution {
    public:
        int threeSumClosest(vector<int>& nums, int target) {
            int len = nums.size();
            if(len<3){
                return 0;
            }
            sort(nums.begin(), nums.end());
            int first,second,third;
            int diff =INT_MAX; //间隔
            int value;  //值
            for(first=0;first<len-2;++first){
                second = first+1;
                third = len-1;
                while(second < third){
                    int sum = nums[first]+nums[second]+nums[third];
                    if(sum == target){
                        return sum;
                    }else if(sum < target){
                        if((target-sum) < diff){
                            diff = target-sum;
                            value = sum;
                            
                        }
                        second++;
                    }else{
                        if((sum-target) < diff){
                            diff = sum-target;
                            value = sum;
                        }
                        third--;
                    }
                }//while
            }//for
            return value;
            
        }
    };

**（4）4Sum**

**原题地址**：[https://leetcode.com/problems/4sum/description/][https_leetcode.com_problems_4sum_description]

**题目描述：**

Given an array *S* of *n* integers, are there elements *a*, *b*, *c*, and *d* in *S* such that *a* \+ *b* \+ *c* \+ *d* = target? Find all unique quadruplets in the array which gives the sum of target.

**Note:** The solution set must not contain duplicate quadruplets.

For example, given array S = \[1, 0, -1, 0, -2, 2\], and target = 0.

A solution set is:

\[-1, 0, 0, 1\],

\[-2, -1, 1, 2\],

\[-2, 0, 0, 2\]

**思路：**

先固定前两个数，后两个数跟前面题同样的思路

**AC代码：**

class Solution {
    public:
        vector<vector<int>> fourSum(vector<int>& nums, int target) {
            vector<vector<int> > res;
            int len = nums.size();
            if(len<4){
                return res;
            }
            sort(nums.begin(), nums.end());
            for(int i=0;i<len-3;++i){
                if(i>0 && nums[i] == nums[i-1])  continue;  //去掉重复的数
                if((nums[i]+nums[i+1]+nums[i+2]+nums[i+3]) > target)  break;  //做一些剪枝，最小的四个数相加都比target大时，肯定无解
                if((nums[i]+nums[len-1]+nums[len-2]+nums[len-3]) < target)  continue; //做一些剪枝，当i固定时，当前最大的相加都比target小i++
                for(int j=i+1;j<len-1;++j){
                    //再固定第二个数
                    if(j>i+1 && nums[j] == nums[j-1])   continue;  
                    if((nums[i] + nums[j] + nums[j+1] + nums[j+2]) > target)    break;
                    if((nums[i] + nums[j] + nums[len-1] + nums[len-2]) < target)    continue;
                    int left = j+1;
                    int right = len-1;
                    while(left < right){
                        int sum = nums[i]+nums[j]+nums[left]+nums[right];
                        if(sum == target){
                            res.push_back(vector<int>{nums[i], nums[j], nums[left], nums[right]});
                            do{left++;}while(left<right && nums[left] == nums[left-1]);
                            do{right--;}while(left<right && nums[right] == nums[right+1]);
                        }else if(sum < target){
                            left++;
                        }else{
                            right--;
                        }
                    }
                }
            }//for
            return res;
        }
    };

**（5）今年腾讯的一道笔试题：拼凑硬币**

题目描述：小Q十分富有，拥有非常多的硬币，小Q拥有的硬币是有规律的，对于所有的非负整数K，小Q恰好各有两个面值为2^k的硬币，所有小Q拥有的硬币就是1，1，2，2，4，4，8，8.....小Q有一天去商店购买东西需要支付n元钱，小Q想知道有多少种方案从他拥有的硬币中选取一些拼凑起来恰好是n元（如果两种方案某个面值的硬币选取的个数不一样就考虑为不一样的方案）

**输入：**

输入包括一个整数n(1<=n<=10^18)，表示小Q需要支付多少钱，注意n的范围

**输出：**

输出一个整数，表示小Q可以拼凑出n元钱的方案数

样例输入：6

样例输出：3 （例如4+2， 4+1+1， 2+2+1+1）

**常规方法：使用动态规划**

使用数组dp\[n, i\]表示使用1,1,2,2,4,4, ..., 2^i, 2^i可以组合成n的方案数

dp\[0, i\] = 1,当n=0时，即所有面值的硬币都不选，所以只有一种方案

dp\[1, i\] = 1, 当n=1时，只能选取一个一元的硬币，所以只有一种方案

res\[2, 0\]=1，即只选取两个一元硬币，所以只有一种方案

res\[n, 0\] = 0，当n>=3时，无法只使用1组成大于2的数，所以方案数为0

res\[n, i\] = sum(num\[n-2^i\*m, i-1\]), n, i取其他，0<=m<=2

代码：

#include <iostream>
    #include<cmath>
    using namespace std;
    
    int main()
    {
        int n;
        while(cin>>n){
            //一些特殊情况处理
            if(n == 0 || n == 1){
                return 1;
            }
    
            int m = log(n)/log(2) + 1;
            //dp[n,m]
            int i,j;
            int** dp = new int*[n+1];
            for(i=0;i<=n;++i){
                dp[i] = new int[m];
            }
    
            //初始化二维数组
            for(i=0;i<m;++i){
                dp[0][i] = 1;
                dp[1][i] = 1;
            }
    
            dp[1][0] = 1;
            dp[2][0] = 1;
    
            for(i=1;i<=n;++i){
                for(j=1;j<m;++j){
                    int sum = 0;
                    for(int m=0;m<3;++m){
                        int rest = (int)(i-pow(2, j)*m);
                        if(rest >= 0){
                            sum+=dp[rest][j-1];
                        }
                    }
                    dp[i][j] = sum;
                }
            }
            cout<<dp[n][m-1]<<endl;
        }
        return 0;
    }

**一个很秒的思路**：

将硬币分为两份：1，2，4，8，16，... 和1，2，4，8，16，...

组成两个数值为a, b的两个数，他们的和是a+b=n;

a在第一份中只有可能有一种组合方式（采用二进制的思想，任何一个数都可以由若干个2^i的数相加的和组成），而b = n-a也只会有一种组合形式。

将a和b使用二进制表示，举个例子n=11，有a=101, b=110这种组合，即a = 1+0+4=5，b=0+2+4=6。但是注意到会有重复的情况，比如111+100和101+110本质上是同一种组合方法，所以需要将二个数做二进制异或然后去重。

**代码：**

#include <iostream>
    #include<set>
    using namespace std;
    
    int main()
    {
        int n;
        while(cin>>n){
            set<int> countset;
            for(int i=1;i<=n/2;i++){
                int result =i^(n-i);
                countset.insert(result);
            }
            cout<<countset.size()<<endl;
        }
        return 0;
    }

[https_leetcode.com_problems_two-sum_description]: https://leetcode.com/problems/two-sum/description/
[https_leetcode.com_problems_3sum_description]: https://leetcode.com/problems/3sum/description/
[https_leetcode.com_problems_3sum-closest_description]: https://leetcode.com/problems/3sum-closest/description/
[https_leetcode.com_problems_4sum_description]: https://leetcode.com/problems/4sum/description/