数组题目总结

sum类型的题

• leetcode 2sum

• leetcode 15. 3Sum
  思路：将3sum转化成2sum问题

class Solution {
public:
    set<vector<int>> res;
    
    vector<vector<int>> threeSum(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int n = nums.size();
        vector<vector<int>> ret;
        if(n <= 1) return ret;
        unordered_map<int, int> map;
        for(int i = 0; i < n; i++)
        {
            if(i>=2)
            {
                twoSum(nums, map, i, -nums[i]);
            }
            map[nums[i]] ++;
        }
        for(auto i:res)
            ret.push_back(i);
        return ret;
    }
    void twoSum(vector<int> nums, unordered_map<int,int> map, int i, int target)
    {  
        for(int k = 0; k < i; k++)
        {
            if(map.size() == 1 && map[0] != 0) 
            {
                res.insert(vector<int>{0,0,0});
                return;
            }
            map[nums[k]] --;
            if(map.find(target-nums[k]) != map.end() && map[target-nums[k]] > 0)
            {   
                vector<int> p = { nums[k], target-nums[k],nums[i]};
                res.insert(p);
            }
        }
        return;
    }
};

• leetcode 16. 3Sum Closest
  思路：固定一个数，将问题转化成找到离target2中最近的两个数

class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
        int n = nums.size();
        int res = nums[0] + nums[1] + nums[2];
        sort(nums.begin(), nums.end());
        if(n <= 1) return -1;
        for(int i = 0; i < n-2; i++)
        {
            int target2 = target - nums[i];
            int left = i + 1;
            int right = n - 1;
            int closest = nums[left] + nums[right];
            while(left < right)
            {
                if(nums[left] + nums[right] <= target2)
                    left ++;
                else
                    right--;
                if(left < right && (abs(target2 - closest) > abs(target2 - nums[left] - nums[right])))
                    closest =  nums[left] + nums[right];
            }
            if(abs(target - closest - nums[i]) < abs(target - res))
                res = closest + nums[i];
        }
        return res;
    }
};