当前位置：网站首页>[record of question brushing] 15 Sum of three numbers

[record of question brushing] 15 Sum of three numbers

2022-07-20 21:40:00 【InfoQ】

One 、 Title Description

source ：

Power button （LeetCode）

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 .

Example 1：

 Input ：nums = [-1,0,1,2,-1,-4]
 Output ：[[-1,-1,2],[-1,0,1]]

Example 2：

 Input ：nums = []
 Output ：[]

Example 3：

 Input ：nums = [0]
 Output ：[]

Tips ：

0 <= nums.length <= 3000

-105 <= nums[i] <= 105

Two 、 Thought analysis

After ordering , Double pointer solution

Sort the array first , After ordering If there is , The negative number is on the left The distribution of positive numbers on the right .

We define a pointer num[i] Traverse the sorted array

In order to make the sum of the three numbers 0 Then there must be both negative and positive numbers , therefore num[i] In certain cases , Let's define two more pointers (L,R) Traverse from both sides , send
L + num[i] + R == 0
That is, a set of triples , During traversal ：

If and
Greater than 0
, explain
R
  Too big ,
R
Move left

If and
Less than 0
, explain  
L
  Too small ,
L
  Move right

Duplicate element occurred skip

dissatisfaction L < R end

nums[i] > 0
Because it's sorted , So there can't be three numbers that add up to  
0
, Go straight back to

The array is  
null
  Or the array length is less than  
3
, Go straight back to

3、 ... and 、 Code implementation

class Solution {
 public static List<List<Integer>> threeSum(int[] nums) {
 List<List<Integer>> res = new ArrayList();
 int len = nums.length;
 if(nums == null || len < 3) return res;

 //  Sort 
 Arrays.sort(nums);

 for (int i = 0; i < len ; i++) {
 //  If the current number is greater than 0, Then the sum of three numbers must be greater than 0, So end the cycle 
 if(nums[i] > 0) break;
 //  duplicate removal 
 if(i > 0 && nums[i] == nums[i-1]) continue;
 int L = i + 1;
 int R = len - 1;
 while(L < R){
 int sum = nums[i] + nums[L] + nums[R];
 if(sum == 0){
 res.add(Arrays.asList(nums[i],nums[L],nums[R]));
 //  duplicate removal 
 while (L<R && nums[L] == nums[L+1]) L++;
 while (L<R && nums[R] == nums[R-1]) R--;
 L++;
 R--;
 }
 else if (sum < 0) L++;
 else if (sum > 0) R--;
 }
 }
 return res;
 }
}

Complexity analysis

Time complexity ：

, among

n

It's an array

nums

The length of

Spatial complexity ：

, Pointers use extra space of constant size

Running results

summary

Because the sum is zero There must be both positive and negative , So we sort , In the case of determining a number , Using double pointers to trace from both sides is the most direct and fast way to find qualified numbers .

This problem can also be regarded as a deformation problem of the use of double pointers .

原网站

版权声明
本文为[InfoQ]所创，转载请带上原文链接，感谢
https://yzsam.com/2022/201/202207192015158130.html