注册一亩三分地论坛,查看更多干货!
您需要 登录 才可以下载或查看附件。没有帐号?注册账号 
x
思路分为三步:
1. sorting
2. 建立一个map,可以把任一加和值映射到一系列tuple里 在我的tuple里前两个数是数组中的数, 且第一个小于第二个,而第三个则是第一个数的index
比如 给定数组 A={1 2 3 4 5 6},那么 5 -> {(1,4,0) (2,3,1)} 3->{(1,2,0)}
3. 用两个index i,j 搜索答案 如果发现target-nums[i]-nums[j]所映射的tuple里面第三位index 比j大,那么nums[i],nums[j]以及tuple里面的两个数就会组成一个可行解
另有一些小优化,bypass 掉了很多不需要考虑的情况和不需要记录到map里面的tuple。
我想知道第三步的复杂度可否认为是O(n^2)……这么写是要比O(n^3)快的(20ms 对比 60ms),但总有一种worst case O(n^3)的感觉- struct Mtuple{
- Mtuple(int A,int B,int K){
- a=A;
- b=B;
- k=K;
- }
-
- int a;
- int b;
- int k;//index
- };
- class Solution {
- public:
- vector<vector<int>> fourSum(vector<int>& nums, int target) {
- vector<vector<int>>result;
- int n=nums.size();
- if(n<4)return result;
-
- int i,j,k,temp;
- vector<int> cache;
-
- sort(nums.begin(),nums.end());
- unordered_map<int,vector<Mtuple> > map;//send number to tuples; 4 |-> (1,3,2)
-
- vector<Mtuple> fill;
-
- for(i=n-1;i>=3;i--){
- if(i!=n-1)
- if(nums[i]==nums[i+1])
- continue;
-
- if(nums[i]+nums[i-1]+nums[i-2]+nums[i-3]<target)//opt 1st
- break;
- if(nums[i]+nums[0]+nums[1]+nums[2]>target)//opt 1st
- continue;
-
- for(j=i-1;j>=2;j--){
-
- if(nums[j]==nums[j+1] && j!=i-1)
- continue;
-
- if(nums[i]+nums[j]+nums[j-1]+nums[j-2]<target)//opt 1st
- break;
- if(nums[i]+nums[j]+nums[0]+nums[1]>target)//opt 1st
- continue;
-
- temp=nums[i]+nums[j];
-
- if(map.find(temp) == map.end()){
- fill.clear();
- fill.push_back(Mtuple(nums[j],nums[i],j));
- map[temp]=fill;
- }
- else{
- map[temp].push_back(Mtuple(nums[j],nums[i],j));
- }
- }
- }
-
- for(i=0;i<=n-4;i++){
- if(i)
- if(nums[i]==nums[i-1])
- continue;
-
- if(nums[i]+nums[n-3]+nums[n-2]+nums[n-1]<target)
- continue;
- if(nums[i]+nums[i+1]+nums[i+2]+nums[i+3]>target)
- break;
-
- for(j=i+1;j<=n-3;j++){
- if(nums[j]==nums[j-1] && j!=i+1)
- continue;
-
- if(nums[i]+nums[j]+nums[n-2]+nums[n-1]<target)
- continue;
- if(nums[i]+nums[j]+nums[j+1]+nums[j+2]>target)
- break;
-
- temp=nums[i]+nums[j];
- if(map.find(target-temp) != map.end()){
- for(k=0;k< map[target-temp].size();k++){
- if(map[target-temp][k].k>j){
- cache=vector<int>({nums[i],nums[j],map[target-temp][k].a,map[target-temp][k].b});
- result.push_back(cache);
- }
- }
- }
- }
- }
-
- return result;
- }
- };
复制代码 |