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

[cute new problem solving] sum of four numbers

2022-07-19 14:49: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 18 topic ： Sum of four numbers ：https://leetcode.cn/problems/4sum/.

Title Description

Here you are n An array of integers  nums , And a target value target . Please find out and return all the following conditions and

No repetition

Four tuples of  [nums[a], nums[b], nums[c], nums[d]] （ If two Quad elements correspond to each other , It is considered that two quads repeat ）：

0 <= a, b, c, d < n

a、b、c and d Different from each other

nums[a] + nums[b] + nums[c] + nums[d] == target

You can press In any order Return to the answer .

Problem solving instructions

The solution of the sum of four numbers is very similar to the sum of three numbers , We refer directly to

【 Cute new problem solving 】 Sum of three numbers

Solution in , The following code can be quickly produced according to the law ：

class Solution {
 public List<List<Integer>> fourSum(int[] nums, int target) {
 //  Array sorting 
 Arrays.sort(nums);
 //  The length of the array 
 int len = nums.length;

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

 for (int i=0; i<len; ++i) {
 //  Fix nums[i]
 List<List<Integer>> res = threeSum(nums, i+1, target - nums[i]);
 for (List<Integer> item : res) {
 item.add(nums[i]);
 ans.add(item);
 }

 //  Skip repeating elements 
 while (i < len-1 && nums[i] == nums[i+1]) {
 ++i;
 }
 }
 return ans;
 }

 /**
 *  Sum of three numbers , The input array is already in order 
 *  In the array nums Find all sums equal to target Non repeating triples of 
 */
 public List<List<Integer>> threeSum(int[] nums, int start, int target) {
 //  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 = start; 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) {
 //  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;
 }
}

so easy, It must have happened , Submit it and see the results ：

I found that I failed to execute the penultimate test case , Because of the input target Is a relatively large negative value , and nums[i] It is also a relatively large positive integer , And our code has

target - nums[i]

Such a piece of code , It can lead to

The integer overflow

（target yes Integer type ）, therefore , The simplest solution is to put target Change the type of to Long, The adjusted code is as follows ：

class Solution {
 public List<List<Integer>> fourSum(int[] nums, int target) {
 //  Array sorting 
 Arrays.sort(nums);
 //  The length of the array 
 int len = nums.length;

 Long targetLong = (long)target;

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

 for (int i=0; i<len; ++i) {
 //  Fix nums[i]
 List<List<Integer>> res = threeSum(nums, i+1, targetLong - nums[i]);
 for (List<Integer> item : res) {
 item.add(nums[i]);
 ans.add(item);
 }

 //  Skip repeating elements 
 while (i < len-1 && nums[i] == nums[i+1]) {
 ++i;
 }
 }
 return ans;
 }

 /**
 *  Sum of three numbers , The input array is already in order 
 *  In the array nums Find all sums equal to target Non repeating triples of 
 */
 public List<List<Integer>> threeSum(int[] nums, int start, long target) {
 //  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 = start; 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, long 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;
 }
}