Today is day 21 of Kevin’s algorithmic journey. Let me show you LeetCode number 15, which is exactly what WE did yesterday

Leetcode | classic force buckle the first question

Let’s share the sum of three. May be a little difficult, I hope you can move smart small brains, stick to it together ~

Every day a smile

If people better than me don’t work hard, why are they better than me?

Topic describes

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 meet the criteria and are not duplicated.

Note: Repeated triples cannot be included in the answer.

Example:

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

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

Source: LeetCode Link: https://leetcode-cn.com/problems/3sum Copyright belongs to The Collar buckle network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.

Their thinking

Double pointer

This question is a typical double pointer application, double pointer and the interview rate of this question are very high, it is recommended to master!

The algorithm is as follows:

  1. If the array length is null or the array length is less than 3, return [].
  2. Sort the array (sort is necessary, otherwise you cannot determine and move the pointer).
  3. Traversing the sorted array:
    • Nums [I]>0; nums[I]>0; nums[I]>0;
    • For repeating elements: skip to avoid repeating solutions
    • Let L= I +1, R=n-1, when L<R, execute loop:
      • When nums[I]+ NUMs [L]+nums[R]==0, the element is added to the result set, and the loop is executed to determine whether the left and right bounds repeat with the next position, and the repeated solution is removed. And at the same time move L and R to the next position to find a new solution
      • If the sum is greater than 0, nums[R] is too large and R shifts to the left
      • If and is less than 0, nums[L] is too small and L shifts to the right

Code implementation 

//go
func threeSum(nums []int)[] []int {
 var result [][]int // Record the result
 length := len(nums) // Get the array length
 if nums == nil || length < 3 {
 return result  }  sort.Ints(nums) / / sorting  for i := 0; i < length; i++ {  // If the current number is greater than 0, the sum of the three numbers must be greater than 0, so end the loop  if nums[i] > 0 {  break  }  // subtract the number of subscripts I  if i > 0 && nums[i] == nums[i- 1] {  continue  }  l := i + 1  r := length - 1  for {  if l >= r {  break  }  sum := nums[i] + nums[l] + nums[r]  if sum > 0 {  r --  continue  }  if sum < 0 {  l ++  continue  }  if sum == 0 {  result = append(result, []int{nums[i], nums[l], nums[r]})  // remove the weight, subscript l  for l < r && nums[l] == nums[l+1] {  l++  }  // remove the weight, subscript r  for l < r && nums[r] == nums[r- 1] {  r--  }  l++  r--  }  }  }  return result } Copy the code
//java
class Solution {
    public static List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> ans = new ArrayList();
        int len = nums.length;
 if(nums == null || len < 3) return ans;  Arrays.sort(nums); / / sorting  for (int i = 0; i < len ; i++) {  if(nums[i] > 0) break; // If the current number is greater than 0, the sum of the three numbers must be greater than 0, so end the loop  if(i > 0 && nums[i] == nums[i-1]) continue; / / to heavy  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++; / / to heavy  while (L<R && nums[R] == nums[R-1]) R--; / / to heavy  L++;  R--;  }  else if (sum < 0) L++;  else if (sum > 0) R--;  }  }  return ans;  } } Copy the code

Solemnly declare:

The code shown has been passed by LeetCode, please rest assured to eat ~

In the front teeth

Many of us try to form good habits, but most of us don’t. In order for us to stick together, we decided to make the following plan (benefits).

Learn algorithms together, punch and get red envelopes!

Participation:

Follow my wechat official account “Kevin’s School”

And with lots of friends

Stick together, learn together, better together!

The rules are:

“Message” “punch XXX days” ➕ “share” to the circle of friends

Reward:

Continuous clocking 21 days, contact me to get 6.6 yuan a red envelope!

Continuous clocking 52 days, contact me to get 16.6 yuan a red envelope!

Continuous clocking 100 days, contact me to get 66.6 yuan a red envelope!

Personal energy is not enough, the content is mainly published on the public platform, other platforms may not update in time, please forgive me ~