首页 > 代码库 > Two Sum

Two Sum

2024-07-21 00:48:56   218人阅读

Two Sum

 

Given an array of integers, 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.

Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2

 

方法一：暴力破解，O(n2)

方法二：使用哈希，将数组元素全部装进哈希map中（由于有元素会重复，所以应该是用unordered_multimap），然后依次遍历数组元素，如果target-数组元素  存在 哈希map中，那么记录下标记录，时间复杂度为0(n)，空间复杂度为O(n)，代码如下：

 1 class Solution { 2 public: 3     typedef unordered_multimap<int, int>::iterator Iterator; 4      5 public: 6     vector<int> twoSum(vector<int> &numbers, int target) { 7         vector<int> ans; 8         unordered_multimap<int, int> ump; 9         for(int i=0; i<numbers.size(); ++i)10             ump.insert( make_pair(numbers[i], i) ); //将数组元素全部放入哈希map中11         for(int i=0; i<numbers.size(); ++i) {12             pair<Iterator, Iterator> piter = ump.equal_range( target - numbers[i] );    //查找满足条件的另一个元素13             if( piter.first != ump.end() ) {    //说明找到了14                 if( numbers[i] != target - numbers[i] ) {   //如果target是numbers[i]的两倍15                     ans.push_back(i+1);16                     ans.push_back( (*piter.first).second+1 );17                     break;18                 }19                 else {  //如果target是numbers[i]的两倍20                     Iterator iter = piter.first;21                     if( (++iter) != piter.second ) {    //存在两个numbers[i]22                         ans.push_back( min(iter->second, piter.first->second)+1 );  //取下标最小的23                         ans.push_back( max(iter->second, piter.first->second)+1 );  //去下标最大的24                         break;25                     }26                 }27             }28         }29         return ans;30     }31 };

方法三：首先对数组进行排序，然后设置首尾两个指针，让首尾指针所指的数相加，得到的数与target的相比，如果比target大，那么尾指针前移，如果比target小，那么首指针后移，如果相等，那么就是我们所求的解，但是由于需要记录下标，需要建立一个下标数组，并对其进行“排序”，具体代码如下：

 1 class Solution { 2 public: 3     vector<int> twoSum(vector<int> &numbers, int target) { 4         pvec = &numbers;    //pvec将用来排序 5         vector<int> index(numbers.size(), 0); 6         for(int i=0; i<numbers.size(); ++i) 7             index[i] = i;   //初始化下标 8         sort(index.begin(), index.end(), cmp);  //对下标进行"排序" 9         int left = 0;10         int right = numbers.size()-1;11         vector<int> ans;12         while( left < right ) {13             int sum = numbers[ index[left] ] + numbers[ index[right] ];14             if( sum == target ) {   //如果相等15                 ans.push_back( index[left]+1);16                 ans.push_back( index[right]+1 );17                 if( ans[0] > ans[1] ) swap(ans[0], ans[1]);18                 break;19             }20             if( sum > target ) --right; //如果sum大于target，那么尾指针需要前移21             else ++left;    //否则首指针需要后移22         }23         return ans;24     }25     26     static bool cmp(const int a, const int b) {27         return (*pvec)[a] < (*pvec)[b]; //要根据numbers中的元素进行排序28     }29     30 private:31     static vector<int>* pvec;32 };33 34 vector<int>* Solution::pvec = 0;

 

 

3Sum

 

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:

  • Elements in a triplet (a,b,c) must be in non-descending order. (ie, a ≤ b ≤ c)
  • 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)

 

方法：暴力破解直接就O(n3)了，果断超时，可以转为towsum的子问题，对整个数组进行排序，假设排序后数组为a0,a1,a3....an-1，当取到ai时，设target为-ai，即转为ai+1，ai+2.。。an-1中求和target的twosum问题，时间复杂度为O(n2)，注意，需要考虑去重复的问题，代码如下：

 1 class Solution { 2 public: 3     vector<vector<int> > threeSum(vector<int> &num) { 4         vector< vector<int> > ans; 5         sort(num.begin(), num.end());   //需要对数组元素进行排序 6         for(int i=0; i+3<=num.size(); ++i) { 7             if( i>0 && num[i] == num[i-1] ) continue;   //如果该数和前面数相同，那么需要直接跳过 8             int target = -num[i]; 9             vector< vector<int> > twoans = twoSum(num, i+1, num.size()-1, target);  //直接转为twosum问题10             for(int j=0; j<twoans.size(); ++j) {11                 twoans[j].insert(twoans[j].begin(), num[i]);    //non-descending order12                 ans.push_back(twoans[j]);13             }14         }15         return ans;16     }17 18     vector< vector<int> > twoSum(vector<int>& num, int left, int right, int target) {19         vector< vector<int> > ans;20         vector<int> v;21         while( left < right ) {22             int sum = num[left] + num[right];23             if( sum == target ) {   //找到一个解24                 v.push_back(num[left]);25                 v.push_back(num[right]);26                 ans.push_back(v);27                 v.clear();28                 ++left;     //left要后移至不同于前一个数位置上29                 while( left < right && num[left] == num[left-1] ) ++left;30                 --right;    //right要前移至不同于后一个数位置上31                 while( left < right && num[right] == num[right+1] ) --right;32             }33             else if( sum > target ) --right;34             else ++left;35         }36         return ans;37     }38 };

3Sum Closest

 

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).

 

同样转为twosum问题，代码如下：
 1 class Solution { 2 public: 3     int threeSumClosest(vector<int> &num, int target) { 4         sort(num.begin(), num.end()); 5         int ans = 0x3fffffff; 6         for(int i=0; i<num.size(); ++i) { 7             int t = twosum(num, i+1, num.size()-1, target-num[i]); 8             if( abs(num[i]+t-target) < abs(ans-target) ) ans = num[i]+t;    //每次比较是否离target最近 9         }10         return ans;11     }12     13     int twosum(vector<int>& num, int left, int right, int target) {14         int ans = 0x3fffffff;15         while( left < right ) {16             int sum = num[left] + num[right];17             if( abs(sum-target) < abs(ans-target) ) ans = sum;  //每次比较是否离target最近18             if( sum == target ) break;  //如果相等，说明距离为0了19             if( sum > target ) --right;20             else ++left;21         }22         return ans;23     }24 };

4Sum

 

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:

  • Elements in a quadruplet (a,b,c,d) must be in non-descending order. (ie, a ≤ b ≤ c ≤ d)
  • 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)

4sum转为3sum，3sum转为2sum，代码如下：

 1 class Solution { 2 public: 3     vector<vector<int> > fourSum(vector<int> &num, int target) { 4         sort(num.begin(), num.end());   //需要对数组元素进行排序 5         vector< vector<int> > ans; 6         for(int i=0; i+4<=num.size(); ++i) { 7             if( i>0 && num[i] == num[i-1] ) continue; 8             vector< vector<int> > threesum = threeSum(num, i+1, target-num[i]); 9             for(int j=0; j<threesum.size(); ++j) {10                 threesum[j].insert(threesum[j].begin(), num[i]);    //non-descending order11                 ans.push_back(threesum[j]);12             }13         }14         return ans;15     }16 17     vector<vector<int> > threeSum(vector<int> &num, int left, int target) {18         vector< vector<int> > ans;19         for(int i=left; i+3<=num.size(); ++i) {20             if( i>left && num[i] == num[i-1] ) continue;   //如果该数和前面数相同，那么需要直接跳过21             vector< vector<int> > twoans = twoSum(num, i+1, num.size()-1, target-num[i]);  //直接转为twosum问题22             for(int j=0; j<twoans.size(); ++j) {23                 twoans[j].insert(twoans[j].begin(), num[i]);    //non-descending order24                 ans.push_back(twoans[j]);25             }26         }27         return ans;28     }29 30     vector< vector<int> > twoSum(vector<int>& num, int left, int right, int target) {31         vector< vector<int> > ans;32         vector<int> v;33         while( left < right ) {34             int sum = num[left] + num[right];35             if( sum == target ) {   //找到一个解36                 v.push_back(num[left]);37                 v.push_back(num[right]);38                 ans.push_back(v);39                 v.clear();40                 ++left;     //left要后移至不同于前一个数位置上41                 while( left < right && num[left] == num[left-1] ) ++left;42                 --right;    //right要前移至不同于后一个数位置上43                 while( left < right && num[right] == num[right+1] ) --right;44             }45             else if( sum > target ) --right;46             else ++left;47         }48         return ans;49     }50 };

 

Two Sum


联系
我们