Sum of "n" numbers of force deduction summary

Preface

I punched the sum of the two numbers of the force buckle 、 After the sum of three numbers and the sum of four numbers , I intend to make a simple summary of this type of topic , To thoroughly understand this problem at one time ！

---

Title Description

Let's first analyze the sum of two numbers one by one 、 Sum of three numbers 、 The sum of four numbers and the method they used , And finally make a summary of these , Extend to others n Sum of the numbers

1. Sum of two numbers

Given an array of integers nums  And an integer target value target, Please find... In the array And is the target value target   The two integers of , And return their array subscripts .

You can assume that each input corresponds to only one answer . however , The same element in the array cannot be repeated in the answer .

Train of thought ：

By analyzing the topic, we can know , The requirement of this topic is to find two data in an array so that the sum of these two data is the target value we need , But data in the same location cannot be used twice at the same time .

Method 1 ： We can use violence to solve , Adopt double circulation , Traversing an array , Finally, get the sum of the data

class Solution {
    public int[] twoSum(int[] nums, int target) {
        for(int i=0;i<nums.length-1;i++){
            for(int j=i+1;j<nums.length;j++){
                if(nums[i]+nums[j]==target)
                return new int[]{i, j};
            }
        }
        return new int[0];
    }
}

Method 2 ： Use Hash surface , The reason why it can be used like this , It's because the time of our previous violent cracking methods seems to be spent on begging target-nums[i] On , So is there a possibility , We can judge first target-nums[i] Does it exist , Then search ？

We use HashMap The way , Store key value pairs , Then we use a layer for Loop to find , If we have data about the difference between the current position value and the target value , We'll go back to target-nums[i] Corresponding value （ That is, the corresponding position ） And current i; If it doesn't exist, join in , And so on , Finally, we will get the result we want ！

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> hashtable = new HashMap<Integer, Integer>();
        for (int i = 0; i < nums.length; ++i) {
            if (hashtable.containsKey(target - nums[i])) {
                return new int[]{hashtable.get(target - nums[i]), i};
            }
            hashtable.put(nums[i], i);
        }
        return new int[0];
    }
}

Wrong way ： Using double pointers ×    Double pointers cannot be used here , Because what he needs is to return the array subscript , So you can't use it like this ！ After you sort, you will disturb the subscript of the array , The final result is bound to be wrong ！

2. Sum of three numbers

Give you one containing n Array of integers  nums, Judge  nums  Are there three elements in a,b,c , bring  a + b + c = 0 ？ Please find out all and for 0 Triple without repetition .

Be careful ： Answer cannot contain duplicate triples .

For this subject , We can find that this topic is very similar to our sum of two numbers , The difference between the two is that what this topic needs is to get the target triplet , That is, the specific value , But the sum of two numbers is the subscript .

Then we have the following methods for this topic

Method 1 ： Triple violence solution ！ For the sum of two numbers , We use the method of double violence solution to get the final result , Then we can use arrays or collections to encapsulate 【 But there are still problems in the way of violence solution I wrote here , There is no weight removal , Inside the buckle 45 / 311】

class Solution {
    public static List<List<Integer>> threeSum(int[] nums) {
        // Create a two-dimensional set to load the data we want , Compared with two-dimensional arrays , More powerful 
        List<List<Integer>> ans=new ArrayList();
        int n=nums.length;
        if(nums.length<3) return ans;
        for(int i=0;i<n-2;i++){
            for(int j=i+1;j<n-1;j++){
                for(int m=j+1;m<n;m++){
                    if(nums[i]+nums[j]+nums[m]==0)
                        {   ansans.add(Arrays.asList(nums[i],nums[L],nums[R])); }
                }
            }
        }
    return ans;
    }
}

Improved version of violence solving --- Add de duplication

class Solution {
public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> results = new LinkedList<>();
        // Sort 
        Arrays.sort(nums);
        for(int i = 0; i < nums.length - 2; i++){
            int x = nums[i];
            // duplicate removal , Suppose the given use case is [0, 0, 0, 0], When i The first time I met 0 when , It doesn't matter to meet for the first time , But if this time i The cycle of is over 
            //i+1 Enter the second loop , Then I still encounter 0, For the second time in a row , This leads to repetition , Must skip 
            if(i > 0 && nums[i - 1] == nums[i]) continue; 
            for(int j = i + 1; j < nums.length - 1; j++){
                int y = nums[j];
                // The principle of weight removal is the same as i,j Must be greater than i + 1, because j It's from i + 1 At the beginning , If you step back from now on , Just go to i It's my territory 
                if(j > i + 1 && nums[j - 1] == nums[j]) continue;  
                for(int k = j + 1; k < nums.length; k++){
                    int z = nums[k];
                    if(k > j + 1 && nums[k - 1] == nums[k]) continue;  // The principle of weight removal is the same as j
                    if(x + y + z == 0){
                        List<Integer> list = new LinkedList<Integer>();
                        list.add(x);
                        list.add(y);
                        list.add(z);
                        results.add(list);
                    }
                }
            }
        }
        return results;
    }
}

Method 2 ： Double pointer 【 Okay , In fact, the above violent solution is not important , Because most people can think of , What we need to do here is the double pointer method I mentioned in the sum of two numbers 】

The basic idea of double pointer is to fix a data , Then the next two data are calculated , If the sum of the following two data and the fixed data is less than 0, Then the previous data will move back , otherwise , The following data moves forward , And so on ！ If the data is exactly equal to 0, Then you need to judge the last bit of the previous data and whether it wants to wait , Equality moves back , The following data should also be operated like this , Then after the operation, the two data will move forward and backward at the same time ！ Finally, we can get the result we want ！

class Solution {
public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> ans=new ArrayList();
        int n=nums.length;
        if(n<3) return ans;
        Arrays.sort(nums);
         for (int i = 0; i < len ; i++) {
            if(nums[i] > 0) break; //  If the current number is greater than 0, Then the sum of three numbers must be greater than 0, So end the cycle 
            if(i > 0 && nums[i] == nums[i-1]) continue; //  duplicate removal 
            int L = i+1;
            int R = len-1;
            while(L < R){
                int sum = nums[i] + nums[L] + nums[R];
                if(sum == 0){
                    ans.add(Arrays.asList(nums[i],nums[L],nums[R]));
                    while (L<R && nums[L] == nums[L+1]) L++; //  duplicate removal 
                    while (L<R && nums[R] == nums[R-1]) R--; //  duplicate removal 
                    L++;
                    R--;
                }
                else if (sum < 0) L++;
                else if (sum > 0) R--;
            }
        }        
        return ans;        
        
}
}

3. Sum of four numbers

Here you are n An array of integers  nums , And a target value target . Please find and return the quads that meet all the following conditions and are not repeated  [nums[a], nums[b], nums[c], nums[d]] （ If two Quad elements correspond to each other , It is considered that two quads repeat ）：

0 <= a, b, c, d < n
a、b、c and d Different from each other
nums[a] + nums[b] + nums[c] + nums[d] == target

Mode one ： Violent solution

Of course, this problem can still be solved by violence , But the time complexity has reached O(N^4), Then there is no demonstration here

Mode two ： Double pointer

class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> quadruplets = new ArrayList<List<Integer>>();
        if (nums == null || nums.length < 4) {
            return quadruplets;
        }
        Arrays.sort(nums);
        int length = nums.length;
        for (int i = 0; i < length - 3; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            if ((long) nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target) {
                break;
            }
            if ((long) nums[i] + nums[length - 3] + nums[length - 2] + nums[length - 1] < target) {
                continue;
            }
            for (int j = i + 1; j < length - 2; j++) {
                if (j > i + 1 && nums[j] == nums[j - 1]) {
                    continue;
                }
                if ((long) nums[i] + nums[j] + nums[j + 1] + nums[j + 2] > target) {
                    break;
                }
                if ((long) nums[i] + nums[j] + nums[length - 2] + nums[length - 1] < target) {
                    continue;
                }
                int left = j + 1, right = length - 1;
                while (left < right) {
                    int sum = nums[i] + nums[j] + nums[left] + nums[right];
                    if (sum == target) {
                        quadruplets.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));
                        while (left < right && nums[left] == nums[left + 1]) {
                            left++;
                        }
                        left++;
                        while (left < right && nums[right] == nums[right - 1]) {
                            right--;
                        }
                        right--;
                    } else if (sum < target) {
                        left++;
                    } else {
                        right--;
                    }
                }
            }
        }
        return quadruplets;
    }
}

Using double pointers here is actually similar to the sum of three numbers , The sum of three numbers is to fix a data first , But here are two fixed data , Then double pointer operation is performed on the following data , In contrast, there is only one more layer for Nesting of loops .

---

summary

I finished the above three questions , We can summarize as follows ：

1. In fact, many of the problems we see can be solved by violence , But it is because we pursue higher requirements , Developed other ways , We usually choose space for time

2. When can we use double pointer to solve ？

Through these questions , We can know , The function of double pointer is that it can simplify the operation , It can help us find the answer faster ！ therefore , When we need to traverse the array, we can use double pointers , Whether it's summation 、 Check the value, etc ！