Tag:leetcode
Article From:https://www.cnblogs.com/liuliu5151/p/9124596.html

Given an array nums of n integers, are there elements abc in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note:

The solution set must not contain duplicate triplets.

Example:

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

A solution set is:
[
  [-1, 0, 1],
  [-1, -1, 2]
]

 

The meaning of the question is:

Given an array and a valuetarget,Find out all the three numbers add up to equaltargetThe combination.

 

Ideas:

Take [-1, 0, 1, 2, -1, -4] as an example

First, sort an array to ensure that ascening order becomes

[-4,         -1,      -1,     0,     1,     2]

  i (base)

                   j(left)                                                    k(right)

i To traverse an array

j And K move closer to the middle to find out if the sum of the three numbers is target.

Note a few points:

1、The title requests “The solution set must not contain duplicate triplets.” every time mobile I, J, K pay attention to checking.

2、ArraysThe common methods in the tool class need to be kept in mind:

Arrays.sort() Sort array

Arrays.fill() Fill array

Arrays.toString() Turn the int array into an string array

Arrays.asList() Turn the array into a list set

 

 

Code:

 1     public List<List<Integer>> threeSum(int[] nums) {
 2         List<List<Integer>> result = new ArrayList<>();
 3         if (nums.length < 3) return result;
 4         Arrays.sort(nums);
 5         final int target = 0;
 6 
 7         for (int i = 0; i < nums.length - 2; ++i) {
 8             if (i > 0 && nums[i] == nums[i-1]) continue;
 9             int j = i+1;
10             int k = nums.length-1;
11             while (j < k) {
12                 if (nums[i] + nums[j] + nums[k] < target) {
13                     ++j;
14                     while(nums[j] == nums[j-1] && j < k) ++j;
15                 } else if(nums[i] + nums[j] + nums[k] > target) {
16                     --k;
17                     while(nums[k] == nums[k+1] && j < k) --k;
18                 } else {
19                     result.add(Arrays.asList(nums[i], nums[j], nums[k]));
20                     ++j;
21                     --k;
22                     while(nums[j] == nums[j-1] && j < k) ++j;
23                     while(nums[k] == nums[k+1] && j < k) --k;
24                 }
25             }
26         }
27         return result;
28     }

 

 

Leave a Reply

Your email address will not be published. Required fields are marked *