This is the seventh day of my participation in the First Challenge 2022

Given an array nums containing n integers, determine if there are three elements a, B, and c in nums such that a + b + c = 0. Please find all the triples that sum to 0 and are not repeated.

Note: Repeated triples cannot be included in the answer.

Input: nums = [1, 2, 1, 4] output: [[1, 1, 2], [1, 1]]

The original link

!!!!!!!!! To be honest, when I first saw this problem, I really had a headache. Three numbers add up to zero, right? Before we have done the sum of two numbers, that we can see the double pointer! This is a three number, boy. A three pointer? I don’t know how to do that, do I?

As the saying goes, whenever we don’t know the same question, we go to his answer and find our correct answer from his answer

Let’s look at the picture and see how we deal with violence. Okay

Three loops nested together with a judgment, it’s really wishful thinking to use it to do problems, but what can we think of in this solution?

Why violence is not desirable, because we repeatedly judge a lot of values that we have already judged, and then we think about the sum of our two numbers, sort the array, move the two Pointers from both sides, then we sum the three numbers, we add a pointer in the middle, right?

So how do we move that pointer in the middle?

class Solution { public List<List<Integer>> threeSum(int[] nums) { Arrays.sort(nums); List<List<Integer>> res=new ArrayList<>(); for(int k=0; k<nums.length-2; k++){ if(nums[k]>0||nums[nums.length-1]<0) break; if(nums[k]==nums[k+1]) continue; int i=k+1; int j=nums.length-1; while(i<j){ int sum=nums[k]+nums[i]+nums[j]; if(sum<0){ i++; }else if(sum>0){ j--; }else{ res.add(new ArrayList<Integer>(Arrays.asList(nums[k], nums[i], nums[j]))); i++; j--; } } } return res; }}Copy the code

That’s our code, but it’s wrong. Why? Let’s take a look at the stem of the problem again, that is, we don’t need the three yuan we repeat, so we need to do a de-duplication operation, so where do we fill in this step?

That’s when we move, if we move to the next element and it’s a repeat we move forward

Class Solution {public List<List<Integer>> threeSum(int[] nums) {// Sort array.sort (nums); List<List<Integer>> res=new ArrayList<>(); // For (int k=0; k<nums.length-2; K++) {/ / to make sure the first element, if the minimum is greater than 0 or one of the biggest is smaller than 0, we don't need to make these the if (nums [k] > 0 | | nums [nums. Length - 1] < 0) break; If (K >0 && nums[K]==nums[k-1]) continue; Int I =k+1; Int j=nums.length-1; while(i<j){ int sum=nums[k]+nums[i]+nums[j]; If (sum < 0) {/ / left pointer moves to the right, to the while (I < j && nums = = [I] nums [+ +] I); } else if (sum > 0) {/ / pointer moves left, right to the while (I < j && nums [j] = = nums [- j]); Add (new ArrayList<Integer>(ArrayList (nums[k], nums[I], nums[j]))); While (I <j&&nums[I]==nums[++ I]); while(i<j&&nums[j]==nums[--j]); } } } return res; }}Copy the code

!!!!!!!!! Notice: if you’ve read your own friends, notice that I ++ and — I if we’re using I ++ and we’re still getting the value of I, it’s going to be a problem