Shulou(Shulou.com)06/02 Report--

This article mainly explains "how to find three numbers with a specific value in an array". Interested friends might as well take a look. The method introduced in this paper is simple, fast and practical. Let's let the editor take you to learn "how to find three numbers with a specific value in an array".

What are the specific requirements of the topic? Given the following integer array:

We randomly choose a specific value, such as 13, to find all combinations in which the sum of three numbers equals 13.

Because 5, 6, 2, 13, 5, 1, 7, 13, 9, 1, 13, 13, 9, 1, 13, 13, 9, 1, 13, 13, 9, 1, 13, 13, 9, 1, 13, 13, 7, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 9, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 9, 13, 13, 13, 13, 13, 13

[5, 6,2]

[5, 1,7]

[3, 9,1]

Xiao Hui's idea is to transform the original problem of "the sum of three numbers" into the problem of finding the sum of two numbers n times.

Let's take the above array as an example, select a specific value of 13, and demonstrate the specific idea of Xiao Grey:

In the first round, you access the first element 5 of the array and convert the problem into two numbers with a sum of 8 (13-5) from the following elements:

How to find out the two numbers with a sum of 8? As mentioned last time, we can use a hash table to solve the problem efficiently:

In the second round, you access the second element 12 of the array and convert the problem into two numbers that are found from the following elements and are 1 (13-12):

In the third round, visit element 6, the third element of the array, and convert the problem into two numbers with a sum of 7 (13-6) from the following elements:

And so on, traversing the entire array is equivalent to solving the problem of the sum of n times two numbers.

Public static List threeSum (int [] nums, int target) {List resultList = new ArrayList (); for (int I = 0; I

< nums.length; i++) { Map map = new HashMap(); int d1 = target - nums[i]; //寻找两数之和等于d1的组合 for (int j = i+1; j < nums.length; j++) { int d2 = d1 - nums[j]; if (map.containsKey(d2)) { resultList.add(Arrays.asList(nums[i], d2, nums[j])); } map.put(nums[j], j); } } return resultList; } 在上面的代码中，每一轮解决"两数之和问题"的时间复杂度是O(n)，一共迭代n轮，所以该解法总的时间复杂度是O(n²)。 至于空间复杂度，同一个哈希表被反复构建，哈希表中最多有n-1个键值对，所以该解法的空间复杂度是O(n)。 我们仍然以之前的数组为例，对数组进行升序排列： 这样说起来有些抽象，我们来具体演示一下： 第1轮，访问数组的第1个元素1，把问题转化成从后面元素中找出和为12(13-1)的两个数。 如何找出和为12的两个数呢?我们设置两个指针，指针j指向剩余元素中最左侧的元素2，指针k指向最右侧的元素12： 计算两指针对应元素之和，2+12 = 14 >

12, the result is too big.

Since the array is arranged in ascending order, the element on the left side of k must be less than k, so we move the pointer k one bit to the left:

Calculate the sum of the two fingers for the corresponding elements, 2: 9 = 11

< 12，这次结果又偏小了。 j右侧的元素一定大于j，因此我们把指针j右移一位： 计算两指针对应元素之和，3+9 = 12，正好符合要求! 因此我们成功找到了一组匹配的组合：1，3，9 但这并不是结束，我们要继续寻找其他组合，让指针k继续左移： 计算两指针对应元素之和，3+7 = 10< 12，结果偏小了。 于是我们让指针j右移： 计算两指针对应元素之和，5+7 = 12，又找到符合要求的一组： 1，5，7 我们继续寻找，让指针k左移： 计算两指针对应元素之和，5+6 = 11< 12，结果偏小了。 于是我们让指针j右移： 此时双指针重合在了一起，如果再继续移动，就有可能和之前找到的组合重复，因此我们直接结束本轮循环。 第2轮，访问数组的第2个元素2，把问题转化成从后面元素中找出和为11(13-2)的两个数。 我们仍然设置两个指针，指针j指向剩余元素中最左侧的元素3，指针k指向最右侧的元素12： 计算两指针对应元素之和，3+12 = 15 >

11, the result is too big.

Let's move the pointer k to the left:

The sum of the corresponding elements of the two fingers is calculated, 3: 9 = 12 > 11, and the result is still too large.

Let's keep the pointer k moving to the left:

Calculate the sum of the two fingers for the corresponding elements, 3: 7 = 10

< 11，结果偏小了。 我们让指针j右移： 计算两指针对应元素之和，5+7 = 12 >

11, the result is too big again.

Let's move the pointer k to the left:

Calculate the sum of the two fingers for the corresponding elements, 5: 6 = 11, so we find another group that meets the requirements:

2,5,6

Let's keep looking and move the pointer k to the left:

At this point, the two pointers coincide again, and we end the cycle.

Following this line of thinking, we traverse the entire array all the time.

The way to find a matching combination by using two pointers pointing at both ends of the array and constantly moving closer to the middle is the double pointer method, also known as the "pinch method".

Public static List threeSumv2 (int [] nums, int target) {Arrays.sort (nums); List resultList = new ArrayList (); / / large cycle for (int I = 0; I < nums.length; iTunes +) {int d = target-nums [I]; / j and k double pointer cycle positioning, j is on the left end, k is on the right end for (int juniors 1)

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.