Shulou(Shulou.com)05/31 Report--

This article mainly explains "how to find out whether the three numbers are zero by Java". Interested friends might as well take a look. The method introduced in this paper is simple, fast and practical. Next, let the editor take you to learn "how to find out whether the three numbers are zero by Java".

The simple approach, according to 2Sum, traverses 3 times, when the time complexity is O (n to the third power) import java.util.ArrayList;import java.util.Arrays;import java.util.List;/** * Created by lifei on 16-5-29. * / public class ThreeSum {/ * * violent solution is everyone can think of, three layers of for loop, time complexity is O (n ^ 3), but also to deal with repetitive problems, obviously not the desired solution. Can it be reduced to O (n ^ 2)? The time complexity of the sorting algorithm is O (nlgn), which is less than O (n ^ 2), so we might as well sort the array first. * * after sorting, we can scan the array from the front and back ends to the middle with two pointers. In the case of 2Sum, we find that the sum of the two pointers is target. * similar to 3Sum, we can first fix a number, and then find the sum of the other two numbers as the opposite of the first number. * * anyone who has done leetcode knows that there are 2sum, 3sum (closest), 4sum and other questions. These are also classic questions in the interview to see if the nature of sorting can be used reasonably. * get an efficient algorithm step by step. After summary, I think these problems can be summarized and digested by a general K sum summation problem. * here we directly give the problem description and algorithm of K Sum (recursive solution), and then apply this general method to specific K, * such as 2Sum, 3Sum, 4Sum problems in leetcode. At the same time, we also give the discussion of another hash algorithm. * * K Sum solution method, suitable for leetcode 2Sum, 3Sum, 4Sum: method 1: violence, that is, enumerating all K-subset, then this complexity is to select K from N, complexity is O (N ^ K) method 2: the algorithm complexity of sorting 2sum is O (NlogN) because sorting uses NlogN and the search of head and tail pointer is linear, so the overall complexity is O (NlogN). Now consider 3sum, with 2sum actually 3sum is not difficult, think like this: first take out a number, then I just need to find two numbers in the remaining numbers so that their sum is equal to (target-the number taken out). So 3sum degenerates to 2sum, takes out a number, and there are N such numbers, so the complexity of 3sum is O (N ^ 2). Note that the complexity here is N square, because you only need to sort it once, and the rest of the work is to take out a number, and then find the remaining two digits. Find the two numbers that 2sum scans linearly with the head and tail pointer. It is easy to miscalculate the complexity as O (N ^ 2logN), which is not correct. If we continue, 4sum can also degenerate into a 3sum problem (copyright @ sigmainfy), and so on, K-sum will degenerate step by step, and finally solve a 2sum problem. The complexity of K sum is O (n ^ (Kmurl)). This bound seems to be the best bound, that is, the K-sum problem is best able to achieve O (n ^ (Kmur1)) complexity K Sum (2Sum, 3Sum, 4Sum) algorithm optimization (Optimization): here are two points: first, for example, when 3sum is sorted as a whole, there is no need to repeat when enumerating the third number. For example, the number after sorting is a b c d e f, then the first enumeration a, the rest of the b c d e f for 2sum, after the second enumeration b, only need to carry out 2sum in c d e f, rather than 2sum in a c d e f, you can understand this, it is quite helpful to figure it out. Second, K Sum can write a recursive program to solve it elegantly, and you can try it yourself. Just be careful not to repeat the sort when writing recursion. * / List ret = new ArrayList (); public List threeSum (int [] num) {if (num = = null | | num.length

0 & & num [I] = Num [I-1]) continue; find (num, iTun1, len-1, num [I]); / / find the sum of two numbers with num [I] is 0} return ret;} public void find (int [] num, int begin, int end, int target) {int l = begin, r = end While (l < r) {if (num [l] + num [r] + target = 0) {List ans = new ArrayList (); ans.add (target); ans.add (Num [l]); ans.add (Num [r]); ret.add (ans) / put while (l < r & & num [l] = = num [lumb1]) lumbago in the result set; while (l < r & & num [r] = = numm [r-1]) r Mustang; Lafayette; Rafael;} else if (num [l] + num [r] + target < 0) {lump + } else {Java;} at this point, I believe you have a deeper understanding of "how to find three numbers for zero". You might as well do it in practice! Here is the website, more related content can enter the relevant channels to inquire, follow us, continue to learn!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.