leetcode 15.3 sum

subject

Link: https://leetcode-cn.com/problems/3sum

Given a n array of nums containing n integers, determine if there are three elements a, b, c in nums such that a + b + c = 0?Find all triples that meet the criteria and do not repeat.

Note: The answer cannot contain duplicate tuples.

Example:

Given the array nums = [-1, 0, 1, 2, -1, -4],

The set of tuples that meet the requirements is:
[
[-1, 0, 1],
[-1, -1, 2]
]

C++ Code

The first and most immediate solution is obviously a cycle of violence, traversing all possible situations.

This requires three for loops to be nested, so the time complexity O(N3) is obviously unacceptable.

How to optimize?I have no idea. Consider simplifying the problem first.

This idea is possible because a given array can be sorted into an ordered array, and O(NlogN) is not worth mentioning in the face of violence laws when sorting is time-complex.

When the array is ordered, we have a way to deal with it.The problem becomes:

Fixed the minimum number in a tuple, found b + c = -a

Now that we have an ordered array, we can use the double-pointer method to narrow down the range of values until the condition of the left pointer l<the right pointer r is not satisfied

In addition, you need to think about how to handle the case where the conditions are not unique and how to weight.

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        int target;
        vector<vector<int>> ans;
        sort(nums.begin(), nums.end());
        for (int i = 0; i < nums.size(); i++) {
            if (i > 0 && nums[i] == nums[i - 1]) continue;
            if ((target = nums[i]) > 0) break;
            int l = i + 1, r = nums.size() - 1;
            while (l < r) {
                if (nums[l] + nums[r] + target < 0) ++l;
                else if (nums[l] + nums[r] + target > 0) --r;
                else {
                    ans.push_back({target, nums[l], nums[r]});
                    ++l, --r;
                    while (l < r && nums[l] == nums[l - 1]) ++l;
                    while (l < r && nums[r] == nums[r + 1]) --r;
                }
            }
        }
        return ans; 
    }
};

leetcode 16.Closest sum of three

subject

Link: https://leetcode-cn.com/problems/3sum-closest/

Given an array nums containing n integers and a target value.Find the three integers in nums so that they are closest to the target.Returns the sum of these three numbers.Assume that only one answer exists for each set of inputs.

For example, given array nums = [-1, 2, 1, -4], and target = 1.

The sum of the three nearest numbers to the target is 2. (-1 + 2 + 1 = 2).

C++ Code

Still continuing the leetcode NO.15 sum of three numbers scheme, no idea, first simplify the problem, nums array sorting, into an ordered array.

At this point, we can still use the double-pointer method to solve this problem.

Consider carefully: How can you prove that the double-pointer method will not miss the optimal solution in the process of shrinking gradually?

class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
        int total_best_sum = -1;
        int total_min_dict = INT_MAX;
        if(nums.size() < 3)
            return total_best_sum;
        // Sort the array first
        sort(nums.begin(), nums.end());
        for(int i = 0; i < nums.size() - 2; i++){
            int a = nums[i];
            int residual = target - a;
            int l = i + 1;
            int r = nums.size() - 1;
            int min_dict = INT_MAX;
            int best_sum = -1;
            while(l < r){
                int cur_threeSum = a + nums[l] + nums[r];
                int cur_dict = abs(target - cur_threeSum);
                if(cur_dict == 0)
                    return target;
                if(cur_dict < min_dict){
                    min_dict = cur_dict;
                    best_sum = cur_threeSum;
                }
                if(target - cur_threeSum > 0)
                    l++;
                else
                    r--;
            }
            // Ends the search for the optimal triple at a = nums[i] to determine if it is the best overall
            if(min_dict < total_min_dict){
                total_min_dict = min_dict;
                total_best_sum = best_sum;
            }
        }
        return total_best_sum;
    }
};

Execution time: 4 ms, beating 99.46% of all C++ submissions

Memory consumption: 12.2 MB, beating 5.14% of all C++ submissions