首页 > 代码库 > 4Sum

4Sum

2024-09-08 05:19:04   217人阅读

思路：需要返回vector中的值而不是index，所以先对vector排序，使用一个hashTable存储vector中两个数字的和，数据结构类型为unordered_map<int, vector<pair<int, int>>>，然后使用半夹逼计算，直接在hashTable中进行查找，这里用到pair的用法，其使用.first访问第一个元素，.second访问第二个元素，最后对结果进行排序，去除重复的元素，这是一个excited的操作，避免运算过程中重复数字的处理

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        vector<vector<int> > result;
        if(nums.size() < 4)
            return result;
        
        sort(nums.begin(), nums.end());
        unordered_map<int, vector<pair<int, int> > >hashTable;
        for(int i=0; i<nums.size();++i)
        {
            for(int j=i+1; j<nums.size(); ++j)
                hashTable[nums[i] + nums[j]].push_back(pair<int, int>(i, j));
        }
        
        int sum = 0;
        vector<pair<int, int>>index;
        for(int i=0; i<nums.size(); ++i)
        {
            for(int j=i+1; j<nums.size(); ++j)
            {
                sum = target - nums[i] - nums[j];
                if(hashTable.find(sum) != hashTable.end())
                {
                    index = hashTable[sum];
                    for(int k=0; k<index.size(); ++k)
                    {
                        if(index[k].first > j && index[k].second > j)
                        {
                            result.push_back({nums[i], nums[j], nums[index[k].first], nums[index[k].second]});
                        }
                    }
                }
            }
        }
        
        sort(result.begin(), result.end());
        result.erase(unique(result.begin(), result.end()), result.end());
        
        return result;
    }
};

 

4Sum


联系
我们