当前位置：网站首页>[cute new problem solving] sum of three numbers

[cute new problem solving] sum of three numbers

2022-07-19 02:04:00 【InfoQ】

About me ： WeChat official account ：
Interviewer asked
, Original high-quality interview questions , Start with the interview question , But it's not just interview questions .【 Cute new problem solving 】 The series of articles try to look at and solve the problem from the perspective of newcomers , This question is to force deduction  15  topic ：
Sum of three numbers
.

Title Description

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 .

Problem solving instructions

This problem requires finding out the qualified in the integer array
A triple
, Make the sum of three elements in a triple equal 0, and
Cannot contain repeating elements
, therefore , We can sort the array first , For the same elements , After sorting, they are next to each other , similar  [1,1,2,2,2,3,3], In this way, we can easily skip repeating elements , For details, please refer to
【 Cute new problem solving 】 Sum of two numbers  II -  Input an ordered array
.

In order to find the triple , We can adopt the idea of divide and rule , Traversal array , In each cycle , First
Fix one of the elements
, Then find the qualified binary from the remaining elements in the array , Then this problem degenerates into the sum of two numbers , But in
【 Cute new problem solving 】 Sum of two numbers  II -  Input an ordered array
  In this topic , The result returns the subscripts of the two elements that meet the conditions , Not an element value , And the array is from 0 Start looking for , And in our scenario , The required return is a binary （ Element value ）, And input parameters , It starts with a subscript in the array , Not fixed 0 Start , So this is the way to think about it , The framework of the code we can write is as follows ：

class Solution {
 public List<List<Integer>> threeSum(int[] nums) {
 // According to the title , It's summation 0 Triple of , therefore target Pass on 0 that will do
 return threeSum(nums, 0);
 }

 /**
 *  Sum of three numbers
 *  In the array nums Find all sums equal to target Non repeating triples of
 */
 public List<List<Integer>> threeSum(int[] nums, int target) {
 //  First sort the array , That's the premise
 Arrays.sort(nums);

 //  The length of the array
 int len = nums.length;

 //  result set
 List<List<Integer>> ans = new ArrayList<>();
 //  A triplet in the result set
 List<List<Integer>> tmp = null;

 for (int i = 0; i < len; ++i) {
 //  Fix nums[i] As the first element , adopt twoSum Get all the other two elements that meet the conditions
 //  Then form a triple together , Be careful ,twoSum  Join the reference , The subscript at the beginning of the array start To set up
 //  by i+1, Can no longer contain  nums[i]
 tmp = twoSum(nums, i + 1, target - nums[i]);
 for (List<Integer> item : tmp) {
 item.add(nums[i]);
 //  Find a triplet that meets the conditions , And added to the result combination
 ans.add(item);
 }

 //  When something like  [1,1,2,2,2,3,3]  When there are arrays of repeating elements , To skip repeating elements
 while (i < len - 1 && nums[i] == nums[i + 1]) {
 ++i;
 }
 }
 return ans;
 }

 /**
 *  Sum of two numbers
 *  Input array nums It's in order , No need to repeat sorting , And subscript from start Start
 *  That is to find out from start Start to nums.length Between , All satisfaction and for target Non repeating binary of
 */
 public List<List<Integer>> twoSum(int[] nums, int start, int target) {
 // TODO
 }
}

We refer to the sum of two numbers
【 Cute new problem solving 】 Sum of two numbers  II -  Input an ordered array
 , It can be transformed into the following form ：

public class Solution {
 /**
 *  Sum of two numbers
 *  Input array nums It's in order , No need to repeat sorting , And subscript from start Start
 *  That is to find out from start Start to nums.length Between , All satisfaction and for target Non repeating binary of
 */
 public List<List<Integer>> twoSum(int[] nums, int start, int target) {
 //  The length of the array
 int len = nums.length;

 //  Left pointer , Point to the beginning of the array
 int left = start;

 //  Right pointer , Point to the end of the array
 int right = len - 1;

 //  Return results
 List<List<Integer>> ans = new ArrayList<>();

 //  Start the cycle
 while (left < right) {
 int sum = nums[left] + nums[right];

 //  Save the first number of the current cycle , The latter is used for weight determination
 int numLeft = nums[left];

 //  Save the second number of the current cycle , The latter is used for weight determination
 int numRight = nums[right];

 if (target == sum) {
 //  Find the target element , Save to result set
 List<Integer> tmp = new ArrayList<>();
 tmp.add(nums[left]);
 tmp.add(nums[right]);
 ans.add(tmp);

 //  When something like  [1,1,2,2,2,3,3]  When there are arrays of repeating elements , To skip repeating elements
 //  Because the title requires that the result set is not repeated
 while (left < right && nums[left] == numLeft) {
 left++;
 }

 //  When something like  [1,1,2,2,2,3,3]  When there are arrays of repeating elements , To skip repeating elements
 //  Because the title requires that the result set is not repeated
 while (left < right && nums[right] == numRight) {
 right--;
 }
 } else if (target < sum) {
 //  When something like  [1,1,2,2,2,3,3]  When there are arrays of repeating elements , To skip repeating elements
 //  Reduce unnecessary cycles
 while (left < right && nums[right] == numRight) {
 right--;
 }
 } else if (target > sum) {
 //  When something like  [1,1,2,2,2,3,3]  When there are arrays of repeating elements , To skip repeating elements
 //  Reduce unnecessary cycles
 while (left < right && nums[left] == numLeft) {
 left++;
 }
 }
 }

 return ans;
 }
}

原网站

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

边栏推荐

猜你喜欢

随机推荐