Sum of two numbers, sum of three numbers (sort + double pointer)

One 、 And for s Two numbers of

And for s Two numbers of

Ascending , Use double pointer to traverse

class Solution {
    
public:
    vector<int> twoSum(vector<int>& nums, int target) {
    
        int l = 0;
        int r = nums.size() - 1;
        while(l < r){
    
            if(nums[l] + nums[r] == target){
    
                return {
    nums[l], nums[r]};
            }else if(nums[l] + nums[r] > target){
    
                r--;
            }else{
    
                l++;
            }
        }
        return {
    };
    }
};

Two 、 Sum of two numbers

Sum of two numbers

And hash table storage has been traversed and not found and for target Number of numbers ,key Value ,value Subscript the element

use target Subtract the number of current traversals , Look up... In the hash table , Find it and return the current subscript （i） And the subscript taken from the hash table （target - nums[i]）. If not, save the current element value and subscript in the hash table

class Solution {
    
public:
    vector<int> twoSum(vector<int>& nums, int target) {
    
        unordered_map<int, int> mp; // mp[val] = index
        for(int i = 0; i < nums.size(); i++){
    
            if (mp.find(target - nums[i]) != mp.end()){
    
                return {
    i, mp[target - nums[i]]};
            }else{
    
                mp[nums[i]] = i;
            }
        }
        return {
    };
    }
};

3、 ... and 、 Sum of three numbers

Sort with + The double pointer method , The time complexity is $O(N^2)$

class Solution {
    
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
    
        sort(nums.begin(), nums.end(), less<int>());
        set<vector<int>> ans;

        for(int l = 0; l < (int)nums.size() - 2 && nums[l] <= 0; l++){
    
            int mid = l + 1;
            int r = nums.size() - 1;
            while(mid < r){
    
                int sum = nums[l] + nums[mid] + nums[r];
                if(sum == 0){
    
                    ans.insert({
    nums[l], nums[mid], nums[r]});
                    r--;
                    while (mid < r && nums[r] == nums[r + 1]) r--;           // while Circulation is used for weight removal 
                    mid++;
                    while (mid < r && nums[mid] == nums[mid - 1]) mid++;     // while Circulation is used for weight removal 
                }else if(sum > 0){
    
                    r--;
                    while (mid < r && nums[r] == nums[r + 1]) r--;           // while Circulation is used for weight removal 
                }else{
    
                    mid++;
                    while (mid < r && nums[mid] == nums[mid - 1]) mid++;     // while Circulation is used for weight removal 
                }
            }
        }
        return vector<vector<int>> (ans.begin(), ans.end());
    }
};

Four 、 The closest sum of three

The closest sum of three

unsorted , Direct violence backtracking , Overtime

class Solution {
    
public:
    vector<int> choice;
    int gap = INT_MAX;
    int target_;
    int ans;

    void func(int i, const vector<int>& nums){
    
        if(choice.size() == 3){
    
            int sum = accumulate(choice.begin(), choice.end(), 0);
            if (abs(target_ - sum) < gap) {
    
                ans = sum;
                gap = abs(target_ - sum);
            }
        }else{
    
            for(int j = i; j < nums.size(); j++){
    
                choice.push_back(nums[j]);
                func(j + 1, nums);
                choice.pop_back();
            }
        }
    }

    int threeSumClosest(vector<int>& nums, int target) {
    
        target_ = target;
        func(0, nums);
        return ans;
    }
};

Sort + Double pointer

class Solution {
    
public:
    int threeSumClosest(vector<int>& nums, int target) {
    
        sort(nums.begin(), nums.end(), less<int>());
        long ans = INT_MAX;

        for(int l = 0; l < (int)nums.size() - 2; l++){
    
            int mid = l + 1;
            int r = nums.size() - 1;
            while(mid < r){
    
                int sum = nums[l] + nums[mid] + nums[r];
                if(abs(sum - target) < abs(ans - target)){
    
                	// sum and target Distance reduction of , Update ans
                    ans = sum;
                }
                if(sum == target){
    
                	//  And for target, Then distance target lately , by 0, Returns the current sum
                    return sum;
                }else if(sum > target){
    
                    r--;
                }else{
    
                    mid++;
                }
            }
        }
        return ans;
    }
};