Xsum问题(243)

xsum问题

• 2sum

  • map结构时间复杂度O(n)
    map把那些离target有差距的都存起来，等target-nums[i]有对应值时，就表示达到了

    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> res;
        int len = nums.size();
        if ( len < 2) 
            return res;
    
        map<int, int> mp;
    
        for (int i = 0; i < len ; i++){
            if (mp[target - nums[i]] != 0){
                res.push_back(mp[target - nums[i]] - 1);//减去加的那个1
                res.push_back(i);
            }
            else{
                mp[nums[i]] = i + 1;//故意加了1是为了防止为0,这样好判断这个键-值是否存在
            }
        }
        //sort(res.begin(), res.end());
        return res;
    }

  • 先对数据进行排序，如果用STL的sort快排，时间复杂度为O(nlogn)，然后设置两个指针，一个初始化为数组的头，一个初始化在数组的尾，然后两边向中间扫描，如果当前两个指针指向的数的和正好是target，那么就保存当前数对 (防止重复就跳过相同值)
    这个方法找多个就很麻烦了

    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> res;
        int len = nums.size();
        if (len < 2)
            return res;
        vector<int> numsTmp = nums;
        sort(nums.begin(), nums.end()); //使得有序
    
        //收尾指针法
        int sta = 0;
        int end = len - 1;
    
        while (sta < end)
        {
            if (nums[sta] + nums[end] == target)
            {
                bool f1 = false;
                bool f2 = false;
                for (int i = 0; i < len; i++)//排序队列找到了，还要去原来队列找到对应的值序列号
                {
                    if (f1 && f2)
                        break;
                    if (!f1 && numsTmp[i] == nums[sta]) // nums[sta] 可能等于 nums[end]
                    {
                        res.push_back(i);
                        f1 = true;
                    }
                    else if (!f2 && numsTmp[i] == nums[end]) // 这里是else if 不是if
                    {
                        res.push_back(i);
                        f2 = true;
                    }
                }
                break;
            }
            else if (nums[sta] + nums[end] < target)//单方面递增或递减
            {
                sta++;
            }
            else{
                end--;
            }
        }
    
        return res;
    }

• 3sum

  • 依次对数组中得每一个元素num[i]找和为target-num[i]的连个数，这样问题又回到了2Sum上

• 4sum

  •   vector<vector<int> > fourSum(vector<int> &num, int target) {
        vector<vector<int> > ret;
    
        if (num.size() == 0) return ret;
    
        sort(num.begin(), num.end());
    
        for (size_t a = 0; a < num.size(); ++a)
        {
            if (a != 0 && num[a] == num[a-1])
                continue;
        
            for (size_t b = a + 1; b < num.size(); ++b)
            {
                if (b != a + 1 && num[b] == num[b-1])
                    continue;
            
                size_t c = b + 1;
                size_t d = num.size() - 1;
            
                while (c < d)
                {
                    const int sum = num[a] + num[b] + num[c] + num[d];
                
                    if (sum > target)
                        --d;
                    else if (sum < target)
                        ++c;
                    else if (c != b + 1 && num[c] == num[c-1])
                        ++c;
                    else if (d != num.size() - 1 && num[d] == num[d+1])
                        --d;
                    else
                    {
                        vector<int> result;
                    
                        result.push_back(num[a]);
                        result.push_back(num[b]);
                        result.push_back(num[c]);
                        result.push_back(num[d]);
                    
                        ret.push_back(result);
                    
                        ++c;
                        --d;
                    }
                }
            }
        }
    
        return ret;
    }